Intersection of two shortest paths in connected weighted graph

Let $$G=(V,E)$$ be a connected directed weighted graph with non-negative weights on edges. Let $$u,v,s,t$$ be vertices in the graph $$G$$. I need to find an algorithm which in $$O(|E|\log |V|)$$ time checks if there is a vertex $$w$$ which lies in the shorthest path from $$u$$ to $$v$$ and $$s$$ to $$t$$.

My idea is to find a shortest path from $$u$$ to $$v$$ using Dijsktra for example, and then for every vertex $$w_i$$ in that path check if there is a shortest path from $$s$$ to $$w_i$$ and $$w_i$$ to $$t$$. This can be done in the seeked time using Dijkstra if I am correct. Is my reasoning correct?

• You want to run $\Theta (n)$ Dijkstras algorithm and wonder if that runs in $O ( m \log n )$ time, is that correct? – Pål GD Jan 19 at 18:54
• What if there is a different $u\to v$ path that contains the intersection vertex? – Pål GD Jan 19 at 18:56
• Hint, can you find all vertices that are on some shortest path from $u$ to $v$? – Apass.Jack Jan 20 at 6:00

My idea is to find a shortest path from $$u$$ to $$v$$ ...

As noted by Pål GD, it is not enough to find just one shortest path from $$u$$ to $$v$$ as a different shortest path might contain the wanted intersection vertex. We have to take into consideration all shortest paths from $$u$$ to $$v$$. Since we are only interested in the vertices, it is enough to find all vertices that are on some shortest path from $$u$$ to $$v$$. Denote that set of vertices as $$S(u,v)$$, where $$S$$ is the shorthand for both "shortest" and "set".

Characterization of $$S(u,v)$$: Let $$d(x,y)$$ be the distance between vertex $$x$$ and $$y$$. $$x\in S(u,v) \Longleftrightarrow d(u,x)+d(x,v)=d(u,v).$$

It is immediate to prove both "if" and "only if" part.

Here is an wanted algorithm.

Run Dijkstra's algorithm with $$u$$ as source and with a priority queue such as described at this wikipedia entry to obtain function $$d_u$$ such that $$d_u(x)=d(u,x)$$ for all $$x\in V$$ in the form of a look-up table. Similarly, obtain function $$d_v(x)$$ such that $$d_v(x)=d(x,v)$$ for all $$x\in V$$ by running Dijkstra's algorithm on $$G$$ with all edges reversed and $$v$$ as source. Similarly, obtain $$d_s(x)$$ and $$d_t(x)$$. For each vertex $$x$$ in $$V$$, check whether $$d_u(x)+d_v(x)=d_u(v)$$ and $$d_s(x)+d_t(x)=d_s(t)$$. If we find one such vertex, the answer is yes; otherwise, the answer is no.

Here are several related exercises.

Exercise 1. Prove the correctness of the characterization of $$S(u,v)$$ as well as the correctness of the algorithm.

Exercise 2. Show that the above algorithm runs in $$O(|E|\log |V|)$$ time when the priority queue of Dijkstra's algorithm is implemented as a self-balancing binary search tree, binary heap, pairing heap, or Fibonacci heap.

Exercise 3. For each vertex $$u$$, let the shortest-path-index $$d(u)$$ be the number of ordered vertex pairs $$(v_1,v_2)$$ such that $$u$$ belongs to one of the shortest paths from $$v_1$$ to $$v_2$$. Let a path-center of $$G$$ be any vertex whose shortest-path-index is the maximum. Find an efficient algorithm that returns all path-centers.

• A simpler algorithm is to find the shortest-path directed-tree from $u$. Then run BFS from $v$ on the the backward graph of that tree, which will find all vertices that are in the shortest paths of $G$ from $u$ to $v$. – Apass.Jack Feb 21 at 6:34