# All pairs shortest paths

## Input

1. A directed graph $G = (V,A)$
2. An arc length $l(a) \in \mathbb{R}$ for each arc $a \in A$

## Output

For each pair $(v,w) \in A$ with $v,w \in V$:

1. The length $\Delta(v,w)$ of a shortest $(v,w)$-path in $G$ with respect to $\ell$ among all paths that have at most $|V|$ arcs.
2. The last arc (pointing to $w$) of one of these paths.

Remark:

1. Obviously, if no $(v,w)$-path meets any negative cycle, a shortest path exists, and at least one shortest path is simple (because such a path may only contain cycles of zero total length, which may be removed). This path has at most $|V|-1$ arcs. On the other hand, if there are negative cycles, there is, evidently, at least one simple negative cycle. A simple cycle has at most $|V|$ arcs. Therefore, the distance from $v$ to $w$ in the output is negative. Of course, the case $v=w$ is included. The nodes $v\in V$ with negative distance $v\rightarrow v$ are exactly the nodes on negative simple cycles.
2. The path (or negative cycle) itself may be easily reconstructed backwards along the incoming arcs (output #2).

Polynomial

## Known algorithms

1. Floyd-Warshall
2. Bellman-Ford
3. Shortest paths by repeated squaring (variant of Bellman-Ford)