How to find such a vertex of a given graph that belongs to each path between two selected ones?

Question

Programming

Hello! The task is as follows:
Find a vertex of a given graph that belongs to each path between two selected (different) vertices and is different from each of them.
I didn't quite understand the solution. It seems most convenient to use a graph depth-first traversal. The graph is stored as an adjacency list. I think you need to do something like this: 1) find the first path between two given vertices, put the path into an array 2) find another path, compare with what is in the array, remove the vertices of the second path that are not in the array from there. Do this until the array is empty (which means there is no desired vertex) or all paths have been found (the desired vertices will remain in the array).
The question remains: how to find all these different paths? I would be very grateful for any hints.
There is also another idea, but I don't think it's a very good one. Sequentially remove each vertex of the graph (except for two given ones) and check by the same depth-first search whether there is a path between these two vertices. (That is, whether they ended up in two different connectivity components). If they are, then the remote vertex is the desired one.

Answer 1

1. Represent all vertices with numbers from 0 to n;
2. We start the array visited, filled with zeros, and the variable count = 0;
3. Find the shortest path between v and u (for example, Dijkstra). If such a path exists, then count++ and, for each of its vertices g other than u and v, visited[g]++. If the path does not exist, go to step 6;
4. Delete the last edge in the found path;
5. Go back to 3.
6. Look for g such that visited[g] == count. If there is one, then it is the desired one;
Perhaps this algorithm is not the most optimal, but simple.