1
$\begingroup$

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

enter image description here enter image description here

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.

Thanks in advance.

$\endgroup$
3
  • $\begingroup$ 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)$. $\endgroup$ Oct 7, 2019 at 2:06
  • $\begingroup$ 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. $\endgroup$ Oct 7, 2019 at 2:09
  • $\begingroup$ 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. $\endgroup$
    – razzak
    Oct 7, 2019 at 2:16

1 Answer 1

2
$\begingroup$

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.


Old answer below (I miss-read the question and assumed it was asking about Floyd-Warshall)

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.