Floyd‑Warshall Algorithm

The Floyd‑Warshall algorithm is a dynamic programming approach used to find the shortest paths between all pairs of vertices in a weighted graph. It works for graphs with both positive and negative edge weights (provided there are no negative weight cycles) and has a time complexity of $\ (O(V^3)$

---

How It Works

The algorithm maintains a 2D array dist where:

• ( dist[i][j] ) represents the shortest distance from vertex (i) to vertex (j).

Initially, dist[i][j] is set to the weight of the edge from (i) to (j) if such an edge exists; otherwise, it is set to infinity (often denoted by $\infty$) . The diagonal elements are zero since the distance from any vertex to itself is zero.

For each vertex (k) (considered as an intermediate vertex), the algorithm updates the distance between every pair of vertices (i) and (j) using the recurrence relation:

$$\text{dist}[i][j] = \min \Big( \text{dist}[i][j],\; \text{dist}[i][k] + \text{dist}[k][j] \Big)$$

---

Example

Consider a graph with 4 vertices (0, 1, 2, 3) and the following initial distance matrix:

Initial dist:

$$\begin{bmatrix} 0 & 5 & \infty & 10 \\ \infty & 0 & 3 & \infty \\ \infty & \infty & 0 & 1 \\ \infty & \infty & \infty & 0 \\ \end{bmatrix}$$

There is an edge from 0 to 1 with weight 5.
There is an edge from 0 to 3 with weight 10.
There is an edge from 1 to 2 with weight 3.
There is an edge from 2 to 3 with weight 1.

---

Step-by-Step Updates

For (k = 0):
Consider paths going through vertex 0.
No update occurs because vertex 0 is the source for its outgoing edges.

---

For (k = 1):
Consider paths via vertex 1.

• Update:
  Update ($\text{dist}[0][2]$) using the path $0 \rightarrow 1 \rightarrow 2\$:
  $\text{dist}[0][2] = \min(\infty,\, 5 + 3) = 8.$
• Updated Matrix:

$$\begin{bmatrix} 0 & 5 & 8 & 10 \\ \infty & 0 & 3 & \infty \\ \infty & \infty & 0 & 1 \\ \infty & \infty & \infty & 0 \\ \end{bmatrix}$$

---

For (k = 2):
Consider paths via vertex 2.

• Update:
  Update ( \text{dist}[0][3] ) using the path (0 \rightarrow 1 \rightarrow 2 \rightarrow 3):
  $\text{dist}[0][3] = \min(10,\, 8 + 1) = 9.$
• Updated Matrix:

$$\begin{bmatrix} 0 & 5 & 8 & 9 \\ \infty & 0 & 3 & \infty \\ \infty & \infty & 0 & 1 \\ \infty & \infty & \infty & 0 \\ \end{bmatrix}$$

---

For (k = 3):
Consider paths via vertex 3.
No further improvements are possible.

---

Final Result

The final shortest path distance matrix is:

$$\text{dist} = \begin{bmatrix} 0 & 5 & 8 & 9 \\ \infty & 0 & 3 & \infty \\ \infty & \infty & 0 & 1 \\ \infty & \infty & \infty & 0 \\ \end{bmatrix}$$

This matrix tells us, for example, that the shortest distance from vertex 0 to vertex 3 is 9.

---

Summary

The Floyd‑Warshall algorithm efficiently computes the shortest paths between every pair of vertices by iteratively considering each vertex as an intermediate point. It is particularly useful for dense graphs or when multiple shortest path queries are needed.

— Written by Saurabh Patil • B.Tech CSE • Software Developer