1. Представим все вершины числами от 0 до n;
2. Заводим массив visited, забитый нулями, и переменную count = 0;
3. Находим кратчайший путь между v и u (например, Дейкстрой). Если такой путь существует, то count++ и для каждой его вершины g, отличной от u и v, visited[g]++. Если пути не существует, перейти к шагу 6;
4. Удаляем последнее ребро в найденом пути;
5. Возвращаемся к 3.
6. Ищем такую g, что visited[g] == count. Если такая есть, она и является искомой;
Возможно, данный алгоритм не самый оптимальный, зато простой.
