# How does the slow All-pairs-shortest-paths algorithm work?

I am trying to fully understand the following algorithm from CLRS book:

I like to think that it works similarly to Bellman-Ford algorithm by relaxing all edges once for every vertex in the graph. Then we repeat the process for every source vertex $$s \in V$$. But then looking at the three nested loops in EXTEND-SHORTEST-PATHS and the additional loop in SLOW-ALL-PAIRS-SHORTEST-PATHS I am confused what is happening in every loop. The book says that in every iteration of the loop in SLOW-ALL-PAIRS-SHORTEST-PATHS it computes a matrix of size at most $$m$$ edges which confuses me even more.

Could someone please explain in simple terms how the algorithm works? Also in line 7 in EXTEND-SHORTEST-PATHS does it mean: $$l^{'}_{ij} > l_{ik} + w_{kj} \Rightarrow l^{'}_{ij} = l_{ik} + w_{kj}$$ or $$l^{'}_{ij} >= l_{ik} + w_{kj} \Rightarrow l^{'}_{ij} = l_{ik} + w_{kj}$$ While there might not be a difference in both of these cases on computing shortest path distances, it does, however, produce different results when computing predecessor-subgraph.

• This algorithm is slower than running Bellman-Ford $n$ times, one per source. Single instance of Bellman-Ford has complexity $O(|V| |E|)$ (on dense graphs this is equivalent to $O(|V|^3)$. – Marcelo Fornet Oct 7 at 2:06
• This algorithm indeed is running Bellman-Ford from all sources in parallel. If you have calculated all shortest path that uses $t$ edges, after executing Extend-shortest-path you have all shortest path that uses $t+1$ edges. – Marcelo Fornet Oct 7 at 2:09
• If we run bellman-ford $n=|V|$ times, the running time would be $O(V^2E)$ which is $O(V^4)$ for dense graphs. I can't wrap my mind around those loops, although, i too think so that it's running bellman-ford in parallel. – razzak Oct 7 at 2:16

Let me tell you what Bellman-Fords is actually doing because the sentence by relaxing all edges once for every vertex in the graph is not very accurate. In Bellman-Ford you care about single-source-shortest-path. Since every path in the graph have at most $$n$$ nodes it has at most $$n-1$$ edges.

Let's say the source node is $$s$$, then create a table $$distance[\cdot]$$ such that $$distance[s] = 0$$ and it is $$\infty$$ elsewhere. Let's solve the following dynamic programming problem, compute shortest path from $$s$$ to $$u$$ (for every $$u$$) that uses at at least $$t$$ edges.

The table we already filled is correct for the case of $$t=0$$. If you have this table already computed for some $$t$$ after relaxing all edges (in any order) it will be correct for $$t+1$$, since you extend all shortest path that uses $$t$$ edges with at least one more edge by relaxing the end of the path. Notice that you don't need to relax every edge $$n$$ times, but $$n - 1$$ times since largest path will have at most $$n - 1$$ edges.

The algorithm you showed is doing that for every pair of nodes in parallel. The first loop only runs $$n - 2$$ (instead of $$n - 1$$ times as I stated above) because you started with a matrix with all shortest path of length 1 already calculated (your base case is $$t = 1$$ instead of $$t = 0$$).

First loop of Extend-shortest-path is selecting the source node and following two loops are iterating through all edges (it assume the graph is complete) and relax the path that starts at $$i$$ ends in $$j$$ and use the edge $$j-k$$ next.

The key element that makes Floyd-Warshall (All-pairs-shortest-path) works is very different from Bellman-Fords key element.

Floyd-Warshall solves the following problem using dynamic programming. Calculate shortest path from every pair of vertex that use only first k vertex as intermediate hops. At the beginning it is the initial weight of existing edges and $$\infty$$ elsewhere (That is the base case).

Assume you have calculated such matrix for the first $$k$$ vertex and let's try to compute it for the first $$k+1$$ vertex. We should take into account paths that uses first $$k$$ vertex and goes through vertex $$k+1$$. Denote by $$dp_k(u, v)$$ the shortest path from $$u$$ to $$v$$ using first $$k$$ vertex, then it follows that the optimal path from $$u$$ to $$v$$ using $$k+1$$ vertex don't use this new vertex or indeed use it, so we get minimum from both values:

$$dp_{k+1}(u, v) = min(dp_k(u, v), dp(u, k) + dp(k, v))$$

In practice, the same table is reused on every step, so the algorithm only requires $$O(n^2)$$ spatial complexity. Temporal complexity is $$O(n^3)$$.

• The algorithm in my question is not Floyd-Warshall. – razzak Oct 7 at 1:56
• I see, sorry for answering without fully understand your question. – Marcelo Fornet Oct 7 at 1:59
• @razzak I updated the answer with real question in mind. Hope it helps now. – Marcelo Fornet Oct 7 at 2:19