Other vertices on the shortest path between two specific vertices

Question

I have been trying to solve a question that says in a directed graph with n vertices and m edges whose weights are all positive integers, we have specified two of them, namely $a$ and $b$. We want to find out the status of all the other vertices whether they are on all the shortest paths from $a$ to $b$, on some of the shortest paths from $a$ to $b$, or on none. My original idea was to perform Dijkstra's algorithm once from $a$, and then we would reverse the directions and then perform the algorithm from $b$. Then we would check for all other vertices, $v_i$ that if $dist(a, v_i) + dist(v_i,b) = dist(a, b)$ holds or not. This way, we would know if $v_i$ is on the shortest paths or not. However, the issue lies in distinguishing between some and none. I'd appreciate it if you could help me with finding the idea to solve it. Also the solution must have a time complexity of $\mathcal{O}((n+m)\log n)$.

Answer 1

Here are some ideas I think could work.

When applying Dijkstra's algorithm and after extracting a vertex $u$ from the priority queue, for each neighbour $v$ of $u$, it is usual to check if: $$d(a, u) + w(u, v) < d(a, v)$$

and update $d(a, v)$ and adding $v$ to the priority queue if that is the case.

Instead of doing that, consider both cases:

• if $d(a, u) + w(u, v) = d(a, v)$, add $u$ to the list of predecessors of $v$;
• if $d(a, u) + w(u, v) < d(a, v)$, set the list of predecessors of $v$ to $[u]$ only (and forget all previous predecessors of $v$).

After the execution of this algorithm, consider the new graph $G' = (V, E')$, where $E' = \{(v, u)\mid v\in V, u \text{ is a predecessor of }v\}$.

Consider $V' = \{v\in V\mid v\text{ is reachable from }b \text{ in }G'\}$. Since all weights are positive, $G'[V']$ is a DAG, hence it has a topological ordering. Now I think that the following facts are true (I may be wrong):

• $v\in V'$ if and only if it is on a shortest path from $a$ to $b$;
• $v\in V'$ has no edge crossing it in the topological ordering if and only if $v$ is on all shortest paths from $a$ to $b$.

Here, "no edge crossing it" means that if the topological ordering is $(v_1, …, v_n)$, then $v_j$ has no edge crossing it if there is no edge $(v_i, v_k)$ with $i < j < k$. This can be checked in $\mathcal{O}(|V| + |E|)$.