Algorithms-1 05

APSP - All Pairs Shortest Paths and SSSP - Single Source Shortest Paths

Input

Output

Naive solutions

Running SSSP from each vertex is a naive solution that leads to the following runtimes:

• Bellman-Ford - okay with negative edges, but no negative cycles
  • which in worst cases is
• Dijkstra - no negative edges
  • which in worst cases is

Floyd-Warshall

Let us enumerate all vertices from . Consider a function that returns the distance from to using only from the set Clearly, as we either use the same path using only vertices from or find a shorter path via vertex It is clear, that if then there must exist a path from to through vertices and another such path from to We can then conclude:

Formal proof is by induction on and contradiction There are two ways to reconstruct actual shortest paths

• Fill them recursively during the distances calculation
• Calculate them solely from the distance matrix The latter is as follows:

Runtime is

Transitive closure

It is possible to use Floyd-Warshall algorithm to find transitive closure of a graph, by replacing with

Johnson-Dijkstra

1. First, a new node is added to the graph, connected by zero-weight edges to each of the other nodes
2. Second, the Bellman–Ford algorithm is used, starting from the new vertex , to find for each vertex the minimum weight of a path from to . If this step detects a negative cycle, the algorithm is terminated
3. Next the edges of the original graph are reweighted using the values computed by the Bellman–Ford algorithm: an edge from to , having weight ⁠, is given the new weight
4. Finally, is removed, and Dijkstra’s algorithm is used to find the shortest paths from each node to every other vertex in the reweighted graph. The distance in the original graph is then computed for each distance , by adding to the distance returned by Dijkstra’s algorithm.

Essentially, Johnson’s algorithm solves APSP via SSSP while allowing negative edges by combining Bellman-Ford and Dijkstra The runtime is