4
$\begingroup$

Given a directed weighted graph with non-negative weights, how can I find all edges that are a part of any of the shortest paths from vertex X to Y?

In the example below the yellow edges are the solution for finding the shortest path between A and D (note that other examples may have more than one path).

graph

I know how to find all nodes that are a part of a shortest path so I thought that all edges that sit between two nodes which are both on a shortest path means that the edge between them is also a part of the shortest path, but that is not true.

Any ideas would be appreciated.

$\endgroup$
  • $\begingroup$ For each edge, you can decrease its weight by a bit and check whether the shortest path decreased in length. This gives you a polynomial time algorithm, but you can probably come up with more efficient algorithms. $\endgroup$ – Yuval Filmus Jul 1 '18 at 12:41
  • $\begingroup$ I might be missing something, why can't you get the sequence of nodes on the shortest path, then get the edges along that sequence? $\endgroup$ – ryan Jul 1 '18 at 19:57
  • 1
    $\begingroup$ @ryan, because that only takes care of a single shortest path. There might be multiple paths from X to Y that all have the same length and are all tied for shortest, and we want to include all of the edges along all of those paths. $\endgroup$ – D.W. Jul 2 '18 at 17:05
  • $\begingroup$ @ryan What D.W said is true, but also if you just get the edges along that sequence you would also get edge CD in the example (because it is between two nodes which ARE on a shortest path), but itself is NOT actually a part of any shortest path. $\endgroup$ – Ciprum Jul 2 '18 at 17:53
  • 1
    $\begingroup$ @Janekmuric, I was assuming you could get the sequence, and then only get edges between adjacent nodes in the sequence. E.g. you get A,C,E,D then get edges (AC),(CE),(ED). $\endgroup$ – ryan Jul 2 '18 at 18:14
6
$\begingroup$

Off the top of my head, you could do this. (Let's say you want to find all edges on a shortest path from $s$ to $t$.)

  • Run an All-Points Shortest Path (APSP) algorithm to store the shortest-path distances from every node to every other node
  • For every edge $a \rightarrow b$ in the graph:
    • Add up the distance from the $s$ to $a$, and the weight of the edge, and the distance from $b$ to $t$
    • Compare this sum to the distance from $s$ to $t$
    • If it's the same, this edge is part of a shortest path

This runs in $\Theta(E)$ plus the time for the APSP, which is $\Theta(V^3)$ using Floyd-Warshall. The space complexity is $\Theta(E)$ for the final results plus $\Theta(V^2)$ for the APSP.

EDIT: D.W. has pointed out an even more efficient algorithm. Instead of using APSP, use SSSP and SDSP (Single Source/Destination Shortest Path) once each, since you only need the distance from $s$ to everything, and from everything to $t$. This reduces the additional space to $\Theta(V)$, and the time to $\Theta(E+V \log V)$ using Dijkstra (assuming there are no cycles of negative weight).

$\endgroup$
  • 2
    $\begingroup$ This can be done more efficiently by computing the distances from $s$ to each vertex $a$ using a single-source shortest paths algorithm (e.g., Dijkstra's algorithm), then the distances from each vertex $b$ to the $t$ using another run of a single-source shortest paths algorithm (reverse the direction of the edges, then treat $t$ as the source). For instance, if all edge lengths are non-negative, we can use Dijkstra's algorithm as the running time will be $\Theta(E + V \log V)$ instead of $\Theta(V^3)$. $\endgroup$ – D.W. Jul 1 '18 at 19:40
  • $\begingroup$ @D.W. Very good point! Fixed $\endgroup$ – Draconis Jul 1 '18 at 20:15

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.