The Floyd-Warshall Algorithm for All-Pairs Shortest Paths

Author

Your Name

Published

January 30, 2025

Introduction

This lecture explores the problem of finding shortest paths in graphs with both positive and negative edge weights, specifically when negative cycles are absent, ensuring polynomial-time solvability. While Dijkstra’s algorithm and topological sorting are efficient for non-negative weights and acyclic graphs respectively, they are inapplicable here. We introduce the Floyd-Warshall algorithm, a combinatorial approach for graphs with positive and negative edge weights without negative cycles.

A key advantage of the Floyd-Warshall algorithm is its ability to detect negative cycles. The algorithm signals their presence and warns that computed shortest paths might be incorrect. Unlike single-source shortest path algorithms, Floyd-Warshall solves the *All-Pairs Shortest Paths* problem, computing the shortest path between every vertex pair. It achieves this with a time complexity of $O(n^3)$, where $n$ is the number of vertices. This efficiency is notable as it computes approximately $n^2$ shortest paths in $O(n^3)$ time, averaging around $O(n)$ time per shortest path, nearly linear in the number of vertices.

The Floyd-Warshall Algorithm

Handling Negative Edge Weights

The Floyd-Warshall algorithm is designed to work with graphs that have edges with negative weights. This is a more general case than what Dijkstra’s algorithm can handle directly, as Dijkstra’s algorithm requires non-negative edge weights to guarantee correctness.

The Problem of Negative Cycles

A crucial condition for the Floyd-Warshall algorithm (and for the well-definedness of shortest paths in general when negative edges are present) is the absence of negative cycles.

Definition 1 (Negative Cycle).

A negative cycle is a cycle in the graph where the sum of the edge weights is negative.

If a negative cycle is reachable from a source vertex, then shortest paths are not well-defined because one can traverse the negative cycle repeatedly to reduce the path length indefinitely. The Floyd-Warshall algorithm can detect the presence of negative cycles.

All-Pairs Shortest Paths Problem

The Floyd-Warshall algorithm solves the All-Pairs Shortest Paths (APSP) problem.

Definition 2 (All-Pairs Shortest Paths (APSP) Problem).

This problem aims to find the shortest path distances between all pairs of vertices $(u, v)$ in a graph.

In contrast to single-source shortest path algorithms like Dijkstra’s or Bellman-Ford, which compute shortest paths from a single source vertex to all other vertices, Floyd-Warshall provides a more comprehensive solution by considering all possible source-destination pairs.

Comparison with Repeated Dijkstra’s Algorithm

For graphs with non-negative edge weights, one might consider using Dijkstra’s algorithm repeatedly to solve the All-Pairs Shortest Paths problem.

Why Dijkstra Needs to be Repeated $n$ Times

To find the shortest paths between all pairs of vertices using Dijkstra’s algorithm, we need to run Dijkstra’s algorithm starting from each vertex as the source. If there are $n$ vertices in the graph, we would need to run Dijkstra’s algorithm $n$ times.

Consider finding the shortest path from a source vertex $S$ to a destination vertex $T$ using Dijkstra’s algorithm. Dijkstra’s algorithm, starting from $S$, effectively builds a shortest path tree rooted at $S$. In the process of finding the shortest path to $T$, Dijkstra’s algorithm may explore and determine the shortest paths to many other vertices that are closer to $S$ than $T$. In the worst case, to find the shortest path from $S$ to $T$, Dijkstra’s algorithm might end up finding the shortest paths from $S$ to all other vertices in the graph.

Therefore, if we want to find the shortest paths from every vertex to every other vertex, we can run Dijkstra’s algorithm $n$ times, once for each vertex as the source. If Dijkstra’s algorithm has a time complexity of $O(n^2)$ for dense graphs or $O(m + n \log n)$ for sparse graphs, repeating it $n$ times would result in a total time complexity of $O(n^3)$ for dense graphs or $O(nm + n^2 \log n)$ for sparse graphs. However, Dijkstra’s algorithm is not directly applicable when negative edge weights are present.

Floyd-Warshall, despite having a cubic time complexity $O(n^3)$, is advantageous because it handles negative edge weights (in the absence of negative cycles) and directly computes all-pairs shortest paths in a single run.

Algorithm Details

Recursive Formulation

The Floyd-Warshall algorithm is based on a dynamic programming approach. It considers the intermediate vertices in a path.

Definition 3 (Intermediate Vertices).

Let $d_{ij}^{(k)}$ be the length of the shortest path from vertex $i$ to vertex $j$ such that all intermediate vertices on the shortest path are chosen from the set $\{1, 2, \ldots, k\}$.

The base case is when $k=0$. In this case, no intermediate vertices are allowed. Thus, $d_{ij}^{(0)}$ is simply the weight of the edge $(i, j)$ if it exists, or $\infty$ if there is no direct edge, and 0 if $i=j$.

For $k > 0$, to find $d_{ij}^{(k)}$, we consider two possibilities for the shortest path from vertex $i$ to vertex $j$ with intermediate vertices from $\{1, 2, \ldots, k\}$:

1. The shortest path does not pass through vertex $k$. In this case, the shortest path only uses intermediate vertices from $\{1, 2, \ldots, k-1\}$. The length of such a path is $d_{ij}^{(k-1)}$.

2. The shortest path passes through vertex $k$. In this case, the shortest path can be decomposed into two paths: a shortest path from vertex $i$ to vertex $k$ using intermediate vertices from $\{1, 2, \ldots, k-1\}$, and a shortest path from vertex $k$ to vertex $j$ using intermediate vertices from $\{1, 2, \ldots, k-1\}$. The lengths of these paths are $d_{ik}^{(k-1)}$ and $d_{kj}^{(k-1)}$, respectively. The total length is $d_{ik}^{(k-1)} + d_{kj}^{(k-1)}$.

Therefore, the recursive relation is:

for $k \ge 1$. We can compute $d_{ij}^{(k)}$ for all pairs $(i, j)$ and for $k = 1, 2, \ldots, n$. The final shortest path distances between all pairs of vertices will be given by $d_{ij}^{(n)}$.

Matrices: C and P

The Floyd-Warshall algorithm can be implemented using matrices to store the shortest path lengths and predecessor information.

C Matrix: Shortest Path Lengths

We use a matrix $C$ where $C^{(k)}[i][j]$ stores the value $d_{ij}^{(k)}$, which is the length of the shortest path from vertex $i$ to vertex $j$ using intermediate vertices from $\{1, 2, \ldots, k\}$. We start with $C^{(0)}$ initialized based on the edge weights of the graph. Then, we iteratively compute $C^{(1)}, C^{(2)}, \ldots, C^{(n)}$ using the recursive relation. The final matrix $C^{(n)}$ will contain the shortest path lengths between all pairs of vertices.

P Matrix: Predecessor Information

To reconstruct the shortest paths, we can maintain another matrix $P$, called the predecessor matrix. $P^{(k)}[i][j]$ stores the predecessor of vertex $j$ on the shortest path from vertex $i$ to vertex $j$ using intermediate vertices from $\{1, 2, \ldots, k\}$.

If we choose to update the shortest path length from $C^{(k-1)}[i][j]$ to $C^{(k-1)}[i][k] + C^{(k-1)}[k][j]$, it means the shortest path from $i$ to $j$ now passes through $k$. In this case, the predecessor of $j$ in the path from $i$ to $j$ is the same as the predecessor of $j$ in the path from $k$ to $j$. If we do not update (i.e., $C^{(k)}[i][j] = C^{(k-1)}[i][j]$), the predecessor remains the same as in the previous iteration.

Initialization of Matrices

Initialize the distance matrix $C^{(0)}$ as follows:

$C^{(0)}[i][j] = w_{ij}$ if there is an edge from vertex $i$ to vertex $j$ with weight $w_{ij}$.
$C^{(0)}[i][i] = 0$ for all vertices $i$.
$C^{(0)}[i][j] = \infty$ if $i \neq j$ and there is no edge from vertex $i$ to vertex $j$.

Initialize the predecessor matrix $P^{(0)}$:

$P^{(0)}[i][j] = i$ if there is an edge from vertex $i$ to vertex $j$.
$P^{(0)}[i][j] = \text{NIL}$ (or some indicator for no predecessor) if $i \neq j$ and there is no edge from $i$ to $j$.
$P^{(0)}[i][i] = \text{NIL}$.

Iterative Calculation of C and P

Initialization: $C^{(0)}[i][j] \gets w_{ij}$ $P^{(0)}[i][j] \gets i$ $C^{(0)}[i][j] \gets \infty$ $P^{(0)}[i][j] \gets \text{NIL}$ $C^{(0)}[i][i] \gets 0$ $P^{(0)}[i][i] \gets \text{NIL}$

Iteration: $C^{(k)}[i][j] \gets C^{(k-1)}[i][k] + C^{(k-1)}[k][j]$ $P^{(k)}[i][j] \gets P^{(k-1)}[k][j]$ $C^{(k)}[i][j] \gets C^{(k-1)}[i][j]$ $P^{(k)}[i][j] \gets P^{(k-1)}[i][j]$

Negative Cycle Detection: return "Negative cycle detected"

return $C^{(n)}$, $P^{(n)}$

The algorithm has a time complexity of $O(n^3)$ due to the three nested loops. The space complexity can be optimized to $O(n^2)$ by updating $C$ and $P$ in place.

Correctness and Impact of Negative Cycles

The correctness of the Floyd-Warshall algorithm relies on the principle of optimality and dynamic programming. The recursive formulation correctly explores all possible shortest paths by considering whether to include vertex $k$ as an intermediate vertex or not.

However, the presence of negative cycles can disrupt the algorithm’s correctness in terms of finding meaningful shortest path lengths. If there is a negative cycle reachable from some vertex $i$ and reachable to some vertex $j$, then the shortest path from $i$ to $j$ is not well-defined, as one can traverse the negative cycle to reduce the path length indefinitely.

Example of Algorithm Failure with Negative Cycles

Example 1 (Algorithm Failure with Negative Cycles).

Consider a graph with vertices $\{1, 2, 3\}$ and edges $(1, 2)$ with weight 1, $(2, 3)$ with weight 1, and $(3, 1)$ with weight -3. The cycle $1 \rightarrow 2 \rightarrow 3 \rightarrow 1$ has a total weight of $1 + 1 + (-3) = -1$, which is a negative cycle.

If we apply the recursive step, we might incorrectly conclude that the shortest path from vertex 1 to vertex 2 can be improved by passing through vertex 3. The algorithm might suggest a path length of 0 or even lower, which is not a valid shortest path in the traditional sense, as we can keep looping in the negative cycle to reduce the path length further.

Detecting Negative Cycles Using the Diagonal of C

A significant feature of the Floyd-Warshall algorithm is its ability to detect negative cycles. After running the algorithm for all $k$ from 1 to $n$, we can check the diagonal entries of the final distance matrix $C^{(n)}$.

Remark. Remark 1 (Negative Cycle Detection).

If there is any vertex $i$ for which $C^{(n)}[i][i] < 0$, it indicates the presence of a negative cycle reachable from vertex $i$ and back to vertex $i$.

Remark. Remark 2 (Consequences of Negative Cycles).

If $C^{(n)}[i][i] < 0$ for some $i$, it means there is a path from $i$ to $i$ with a negative length, which is a negative cycle. In this case, the shortest paths are not properly defined, and the values in the $C^{(n)}$ matrix may not represent actual shortest path lengths in the presence of negative cycles. However, the algorithm successfully flags the existence of such cycles.

Remark. Remark 3 (Absence of Negative Cycles).

If all diagonal entries $C^{(n)}[i][i] \ge 0$ for all $i$, then there are no negative cycles in the graph (or at least, no negative cycles that affect the shortest path computations in a way that leads to negative diagonal entries). In this case, the matrix $C^{(n)}$ correctly represents the shortest path distances between all pairs of vertices.

Optimization and Special Cases

Memory Optimization

As noted earlier, we can optimize the space complexity of the Floyd-Warshall algorithm. Instead of using $n+1$ matrices $C^{(0)}, C^{(1)}, \ldots, C^{(n)}$, we can use a single matrix $C$. In each iteration $k$, we update the matrix $C$ in place. The update rule becomes: For $k$ from 1 to $n$, for $i$ from 1 to $n$, for $j$ from 1 to $n$:

\[C[i][j] = \min(C[i][j], C[i][k] + C[k][j])\]

Similarly, the predecessor matrix $P$ can also be updated in place. This reduces the space complexity from $O(n^3)$ to $O(n^2)$.

Sparse Acyclic Graphs

For sparse acyclic graphs, the Floyd-Warshall algorithm, with its $O(n^3)$ time complexity, might not be the most efficient choice for all-pairs shortest paths.

When to Prefer Repeated Acyclic Shortest Path Algorithm

If the graph is acyclic and sparse (i.e., the number of edges $m$ is much less than $n^2$), it can be more efficient to use the acyclic shortest path algorithm repeatedly. For an acyclic graph, shortest paths can be found in $O(m+n)$ time using topological sorting. If we repeat this algorithm $n$ times (once for each source vertex), the total time complexity becomes $O(n(m+n)) = O(nm + n^2)$. If $m$ is significantly smaller than $n^2$ (e.g., $m = O(n)$ for sparse graphs), then $O(nm + n^2)$ can be $O(n^2)$, which is better than the $O(n^3)$ complexity of Floyd-Warshall.

Therefore, for sparse acyclic graphs, repeating the acyclic shortest path algorithm for each source vertex is generally more efficient than using Floyd-Warshall.

Conclusion

In this lecture, we explored the Floyd-Warshall algorithm, a powerful tool for solving the All-Pairs Shortest Paths problem in graphs that may contain negative edge weights, provided there are no negative cycles. We discussed its recursive formulation, implementation using distance and predecessor matrices, and its ability to detect negative cycles. We also compared it to repeated Dijkstra’s algorithm and considered optimizations and special cases, such as sparse acyclic graphs where alternative algorithms might be more efficient.

Key takeaways from this lecture include:

The Floyd-Warshall algorithm computes shortest paths between all pairs of vertices.
It handles negative edge weights but requires the absence of negative cycles for correct shortest path distances.
The algorithm has a time complexity of $O(n^3)$ and can be implemented with $O(n^2)$ space.
It can detect negative cycles by checking the diagonal of the distance matrix.
For sparse acyclic graphs, repeated application of a linear-time acyclic shortest path algorithm may be more efficient.

Further study could involve exploring algorithms for detecting and handling negative cycles more explicitly, and investigating other all-pairs shortest paths algorithms that might be more efficient in specific graph structures.

--- title: "The Floyd-Warshall Algorithm for All-Pairs Shortest Paths" author: "Your Name" date: "2025-01-30" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction This lecture explores the problem of finding shortest paths in graphs with both positive and negative edge weights, specifically when negative cycles are absent, ensuring polynomial-time solvability. While Dijkstra's algorithm and topological sorting are efficient for non-negative weights and acyclic graphs respectively, they are inapplicable here. We introduce the Floyd-Warshall algorithm, a combinatorial approach for graphs with positive and negative edge weights without negative cycles. A key advantage of the Floyd-Warshall algorithm is its ability to detect negative cycles. The algorithm signals their presence and warns that computed shortest paths might be incorrect. Unlike single-source shortest path algorithms, Floyd-Warshall solves the \*All-Pairs Shortest Paths\* problem, computing the shortest path between every vertex pair. It achieves this with a time complexity of $O(n^3)$, where $n$ is the number of vertices. This efficiency is notable as it computes approximately $n^2$ shortest paths in $O(n^3)$ time, averaging around $O(n)$ time per shortest path, nearly linear in the number of vertices. # The Floyd-Warshall Algorithm ## Handling Negative Edge Weights The Floyd-Warshall algorithm is designed to work with graphs that have edges with negative weights. This is a more general case than what Dijkstra's algorithm can handle directly, as Dijkstra's algorithm requires non-negative edge weights to guarantee correctness. ## The Problem of Negative Cycles A crucial condition for the Floyd-Warshall algorithm (and for the well-definedness of shortest paths in general when negative edges are present) is the absence of negative cycles. :::: definition **Definition 1** (Negative Cycle). ::: tcolorbox *A negative cycle is a cycle in the graph where the sum of the edge weights is negative.* ::: :::: If a negative cycle is reachable from a source vertex, then shortest paths are not well-defined because one can traverse the negative cycle repeatedly to reduce the path length indefinitely. The Floyd-Warshall algorithm can detect the presence of negative cycles. ## All-Pairs Shortest Paths Problem The Floyd-Warshall algorithm solves the All-Pairs Shortest Paths (APSP) problem. :::: definition **Definition 2** (All-Pairs Shortest Paths (APSP) Problem). ::: tcolorbox *This problem aims to find the shortest path distances between all pairs of vertices $(u, v)$ in a graph.* ::: :::: In contrast to single-source shortest path algorithms like Dijkstra's or Bellman-Ford, which compute shortest paths from a single source vertex to all other vertices, Floyd-Warshall provides a more comprehensive solution by considering all possible source-destination pairs. ## Comparison with Repeated Dijkstra's Algorithm For graphs with non-negative edge weights, one might consider using Dijkstra's algorithm repeatedly to solve the All-Pairs Shortest Paths problem. ### Why Dijkstra Needs to be Repeated $n$ Times To find the shortest paths between all pairs of vertices using Dijkstra's algorithm, we need to run Dijkstra's algorithm starting from each vertex as the source. If there are $n$ vertices in the graph, we would need to run Dijkstra's algorithm $n$ times. Consider finding the shortest path from a source vertex $S$ to a destination vertex $T$ using Dijkstra's algorithm. Dijkstra's algorithm, starting from $S$, effectively builds a shortest path tree rooted at $S$. In the process of finding the shortest path to $T$, Dijkstra's algorithm may explore and determine the shortest paths to many other vertices that are closer to $S$ than $T$. In the worst case, to find the shortest path from $S$ to $T$, Dijkstra's algorithm might end up finding the shortest paths from $S$ to all other vertices in the graph. Therefore, if we want to find the shortest paths from every vertex to every other vertex, we can run Dijkstra's algorithm $n$ times, once for each vertex as the source. If Dijkstra's algorithm has a time complexity of $O(n^2)$ for dense graphs or $O(m + n \log n)$ for sparse graphs, repeating it $n$ times would result in a total time complexity of $O(n^3)$ for dense graphs or $O(nm + n^2 \log n)$ for sparse graphs. However, Dijkstra's algorithm is not directly applicable when negative edge weights are present. Floyd-Warshall, despite having a cubic time complexity $O(n^3)$, is advantageous because it handles negative edge weights (in the absence of negative cycles) and directly computes all-pairs shortest paths in a single run. # Algorithm Details ## Recursive Formulation The Floyd-Warshall algorithm is based on a dynamic programming approach. It considers the intermediate vertices in a path. :::: definition **Definition 3** (Intermediate Vertices). ::: tcolorbox *Let $d_{ij}^{(k)}$ be the length of the shortest path from vertex $i$ to vertex $j$ such that all intermediate vertices on the shortest path are chosen from the set $\{1, 2, \ldots, k\}$.* ::: :::: The base case is when $k=0$. In this case, no intermediate vertices are allowed. Thus, $d_{ij}^{(0)}$ is simply the weight of the edge $(i, j)$ if it exists, or $\infty$ if there is no direct edge, and 0 if $i=j$. For $k > 0$, to find $d_{ij}^{(k)}$, we consider two possibilities for the shortest path from vertex $i$ to vertex $j$ with intermediate vertices from $\{1, 2, \ldots, k\}$: 1\. The shortest path does not pass through vertex $k$. In this case, the shortest path only uses intermediate vertices from $\{1, 2, \ldots, k-1\}$. The length of such a path is $d_{ij}^{(k-1)}$. 2\. The shortest path passes through vertex $k$. In this case, the shortest path can be decomposed into two paths: a shortest path from vertex $i$ to vertex $k$ using intermediate vertices from $\{1, 2, \ldots, k-1\}$, and a shortest path from vertex $k$ to vertex $j$ using intermediate vertices from $\{1, 2, \ldots, k-1\}$. The lengths of these paths are $d_{ik}^{(k-1)}$ and $d_{kj}^{(k-1)}$, respectively. The total length is $d_{ik}^{(k-1)} + d_{kj}^{(k-1)}$. Therefore, the recursive relation is: ::: tcolorbox ::: for $k \ge 1$. We can compute $d_{ij}^{(k)}$ for all pairs $(i, j)$ and for $k = 1, 2, \ldots, n$. The final shortest path distances between all pairs of vertices will be given by $d_{ij}^{(n)}$. ## Matrices: C and P The Floyd-Warshall algorithm can be implemented using matrices to store the shortest path lengths and predecessor information. ### C Matrix: Shortest Path Lengths We use a matrix $C$ where $C^{(k)}[i][j]$ stores the value $d_{ij}^{(k)}$, which is the length of the shortest path from vertex $i$ to vertex $j$ using intermediate vertices from $\{1, 2, \ldots, k\}$. We start with $C^{(0)}$ initialized based on the edge weights of the graph. Then, we iteratively compute $C^{(1)}, C^{(2)}, \ldots, C^{(n)}$ using the recursive relation. The final matrix $C^{(n)}$ will contain the shortest path lengths between all pairs of vertices. ### P Matrix: Predecessor Information To reconstruct the shortest paths, we can maintain another matrix $P$, called the predecessor matrix. $P^{(k)}[i][j]$ stores the predecessor of vertex $j$ on the shortest path from vertex $i$ to vertex $j$ using intermediate vertices from $\{1, 2, \ldots, k\}$. If we choose to update the shortest path length from $C^{(k-1)}[i][j]$ to $C^{(k-1)}[i][k] + C^{(k-1)}[k][j]$, it means the shortest path from $i$ to $j$ now passes through $k$. In this case, the predecessor of $j$ in the path from $i$ to $j$ is the same as the predecessor of $j$ in the path from $k$ to $j$. If we do not update (i.e., $C^{(k)}[i][j] = C^{(k-1)}[i][j]$), the predecessor remains the same as in the previous iteration. ## Initialization of Matrices Initialize the distance matrix $C^{(0)}$ as follows: - $C^{(0)}[i][j] = w_{ij}$ if there is an edge from vertex $i$ to vertex $j$ with weight $w_{ij}$. - $C^{(0)}[i][i] = 0$ for all vertices $i$. - $C^{(0)}[i][j] = \infty$ if $i \neq j$ and there is no edge from vertex $i$ to vertex $j$. Initialize the predecessor matrix $P^{(0)}$: - $P^{(0)}[i][j] = i$ if there is an edge from vertex $i$ to vertex $j$. - $P^{(0)}[i][j] = \text{NIL}$ (or some indicator for no predecessor) if $i \neq j$ and there is no edge from $i$ to $j$. - $P^{(0)}[i][i] = \text{NIL}$. ## Iterative Calculation of C and P ::::: algorithm :::: tcolorbox ::: algorithmic **Initialization:** $C^{(0)}[i][j] \gets w_{ij}$ $P^{(0)}[i][j] \gets i$ $C^{(0)}[i][j] \gets \infty$ $P^{(0)}[i][j] \gets \text{NIL}$ $C^{(0)}[i][i] \gets 0$ $P^{(0)}[i][i] \gets \text{NIL}$ **Iteration:** $C^{(k)}[i][j] \gets C^{(k-1)}[i][k] + C^{(k-1)}[k][j]$ $P^{(k)}[i][j] \gets P^{(k-1)}[k][j]$ $C^{(k)}[i][j] \gets C^{(k-1)}[i][j]$ $P^{(k)}[i][j] \gets P^{(k-1)}[i][j]$ **Negative Cycle Detection:** **return** \"Negative cycle detected\" **return** $C^{(n)}$, $P^{(n)}$ ::: :::: ::::: The algorithm has a time complexity of $O(n^3)$ due to the three nested loops. The space complexity can be optimized to $O(n^2)$ by updating $C$ and $P$ in place. ## Correctness and Impact of Negative Cycles The correctness of the Floyd-Warshall algorithm relies on the principle of optimality and dynamic programming. The recursive formulation correctly explores all possible shortest paths by considering whether to include vertex $k$ as an intermediate vertex or not. However, the presence of negative cycles can disrupt the algorithm's correctness in terms of finding meaningful shortest path lengths. If there is a negative cycle reachable from some vertex $i$ and reachable to some vertex $j$, then the shortest path from $i$ to $j$ is not well-defined, as one can traverse the negative cycle to reduce the path length indefinitely. ### Example of Algorithm Failure with Negative Cycles :::: example **Example 1** (Algorithm Failure with Negative Cycles). ::: tcolorbox *Consider a graph with vertices $\{1, 2, 3\}$ and edges $(1, 2)$ with weight 1, $(2, 3)$ with weight 1, and $(3, 1)$ with weight -3. The cycle $1 \rightarrow 2 \rightarrow 3 \rightarrow 1$ has a total weight of $1 + 1 + (-3) = -1$, which is a negative cycle.* *If we apply the recursive step, we might incorrectly conclude that the shortest path from vertex 1 to vertex 2 can be improved by passing through vertex 3. The algorithm might suggest a path length of 0 or even lower, which is not a valid shortest path in the traditional sense, as we can keep looping in the negative cycle to reduce the path length further.* ::: :::: ## Detecting Negative Cycles Using the Diagonal of C A significant feature of the Floyd-Warshall algorithm is its ability to detect negative cycles. After running the algorithm for all $k$ from 1 to $n$, we can check the diagonal entries of the final distance matrix $C^{(n)}$. :::: remark **Remark 1** (Negative Cycle Detection). ::: tcolorbox *If there is any vertex $i$ for which $C^{(n)}[i][i] < 0$, it indicates the presence of a negative cycle reachable from vertex $i$ and back to vertex $i$.* ::: :::: :::: remark **Remark 2** (Consequences of Negative Cycles). ::: tcolorbox *If $C^{(n)}[i][i] < 0$ for some $i$, it means there is a path from $i$ to $i$ with a negative length, which is a negative cycle. In this case, the shortest paths are not properly defined, and the values in the $C^{(n)}$ matrix may not represent actual shortest path lengths in the presence of negative cycles. However, the algorithm successfully flags the existence of such cycles.* ::: :::: :::: remark **Remark 3** (Absence of Negative Cycles). ::: tcolorbox *If all diagonal entries $C^{(n)}[i][i] \ge 0$ for all $i$, then there are no negative cycles in the graph (or at least, no negative cycles that affect the shortest path computations in a way that leads to negative diagonal entries). In this case, the matrix $C^{(n)}$ correctly represents the shortest path distances between all pairs of vertices.* ::: :::: # Optimization and Special Cases ## Memory Optimization As noted earlier, we can optimize the space complexity of the Floyd-Warshall algorithm. Instead of using $n+1$ matrices $C^{(0)}, C^{(1)}, \ldots, C^{(n)}$, we can use a single matrix $C$. In each iteration $k$, we update the matrix $C$ in place. The update rule becomes: For $k$ from 1 to $n$, for $i$ from 1 to $n$, for $j$ from 1 to $n$: ::: tcolorbox $$C[i][j] = \min(C[i][j], C[i][k] + C[k][j])$$ ::: Similarly, the predecessor matrix $P$ can also be updated in place. This reduces the space complexity from $O(n^3)$ to $O(n^2)$. ## Sparse Acyclic Graphs For sparse acyclic graphs, the Floyd-Warshall algorithm, with its $O(n^3)$ time complexity, might not be the most efficient choice for all-pairs shortest paths. ### When to Prefer Repeated Acyclic Shortest Path Algorithm If the graph is acyclic and sparse (i.e., the number of edges $m$ is much less than $n^2$), it can be more efficient to use the acyclic shortest path algorithm repeatedly. For an acyclic graph, shortest paths can be found in $O(m+n)$ time using topological sorting. If we repeat this algorithm $n$ times (once for each source vertex), the total time complexity becomes $O(n(m+n)) = O(nm + n^2)$. If $m$ is significantly smaller than $n^2$ (e.g., $m = O(n)$ for sparse graphs), then $O(nm + n^2)$ can be $O(n^2)$, which is better than the $O(n^3)$ complexity of Floyd-Warshall. Therefore, for sparse acyclic graphs, repeating the acyclic shortest path algorithm for each source vertex is generally more efficient than using Floyd-Warshall. # Conclusion In this lecture, we explored the Floyd-Warshall algorithm, a powerful tool for solving the All-Pairs Shortest Paths problem in graphs that may contain negative edge weights, provided there are no negative cycles. We discussed its recursive formulation, implementation using distance and predecessor matrices, and its ability to detect negative cycles. We also compared it to repeated Dijkstra's algorithm and considered optimizations and special cases, such as sparse acyclic graphs where alternative algorithms might be more efficient. Key takeaways from this lecture include: - The Floyd-Warshall algorithm computes shortest paths between all pairs of vertices. - It handles negative edge weights but requires the absence of negative cycles for correct shortest path distances. - The algorithm has a time complexity of $O(n^3)$ and can be implemented with $O(n^2)$ space. - It can detect negative cycles by checking the diagonal of the distance matrix. - For sparse acyclic graphs, repeated application of a linear-time acyclic shortest path algorithm may be more efficient. Further study could involve exploring algorithms for detecting and handling negative cycles more explicitly, and investigating other all-pairs shortest paths algorithms that might be more efficient in specific graph structures.