Solution: All-Pairs Shortest Paths

Task

The algorithms described in this chapter can also be modified to return an explicit description of some negative cycle in the input graph $G$, if one exists, instead of only reporting whether or not $G$ contains a negative cycle. Analyze the provided algorithm and then provide its Python implementation in the coding workspace provided below.

Logic building

Here’s an algorithm for the modified version of Johnson’s algorithm that returns either the array of all shortest path distances or a negative cycle.

Algorithm

1. Let $G = (V, E)$ be the input graph, with vertices $V$ and edges $E$.

2. Add a new vertex $s$ to $G$ and add zero-weight edges from $s$ to all vertices in $V$.

3. Run the Bellman-Ford algorithm with $s$ as the source vertex to compute a new set of edge weights $h: E -> R$ that satisfy the following property: for any edge $(u, v)$ ...