Finding all edges on any shortest path between two nodes

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).

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.

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).

StackExchange Computer Science Q#93720, answer score: 10