3
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Apass.Jack Feb 21 at 6:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.