7
$\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.

Improve this question
$\endgroup$
5
  • $\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
    Commented Jul 1, 2018 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
    Commented Jul 1, 2018 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. ♦
    Commented Jul 2, 2018 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$
    – jan
    Commented Jul 2, 2018 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
    Commented Jul 2, 2018 at 18:14

1 Answer 1

Reset to default
10
$\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).

Improve this answer
$\endgroup$
4
  • 3
    $\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. ♦
    Commented Jul 1, 2018 at 19:40
  • $\begingroup$ @D.W. Very good point! Fixed $\endgroup$
    – Draconis
    Commented Jul 1, 2018 at 20:15
  • $\begingroup$ @D.W. dumb question - but how does computing shortest paths from the src vertex -> all other vertices; and from the dest vertex -> al other vertices, give me the list of edges on the shortest path? $\endgroup$
    – Shubham Mittal
    Commented Jul 28, 2021 at 9:17
  • 2
    $\begingroup$ @ShubhamMittal Iterate over the edges and for each one see if (distance from source to head) + (edge weight) + (distance from tail to destination) = (distance from source to destination). If it is, that edge is on a shortest path. $\endgroup$
    – Draconis
    Commented Jul 28, 2021 at 16:05

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