---
title: "Session 9"
description: "Floyd and Warshall's Algorithm for All Pair Shortest Path Algorithms"
image: "https://syntax.theether.in/og.png"
---

> Documentation Index
> Fetch the complete documentation index at: https://syntax.theether.in/llms.txt
> Use this file to discover all available pages before exploring further.

# Session 9

This session is about finding shortest paths between every pair of vertices in a graph. Unlike Dijkstra's algorithm, which starts from one source, Floyd-Warshall works with a distance matrix and gradually improves every source-destination pair.

## Objectives

- Understand all-pairs shortest path computation.
- Apply Floyd-Warshall algorithm using distance matrices.
- Implement the algorithm for different graphs.

## Concept

Floyd-Warshall updates a distance matrix by allowing each vertex to become an intermediate vertex.

```text
D[k][i][j] = min(D[k-1][i][j], D[k-1][i][k] + D[k-1][k][j])
```

## Algorithm

```text
for k from 1 to n:
for i from 1 to n:
    for j from 1 to n:
        D[i][j] = min(D[i][j], D[i][k] + D[k][j])
```

## Complexity

| Metric | Value |
| ------ | ----- |
| Time complexity | `O(n^3)` |
| Space complexity | `O(n^2)` |

## Question 1

### Problem Statement

Apply Floyd-Warshall's algorithm for the given graph. Show the matrix $D^5$ and find the shortest path.

<img src="/216-sc1-ss9-1.png" class="mt-5 rounded-xl" />

### Answer

Here is the step-by-step application of the Floyd-Warshall algorithm for the given graph, followed by the code implementations.

#### Graph Analysis

First, we identify the nodes and edges with their weights from the image.

- **Nodes**: 1, 2, 3, 4, 5
- Edges:
  - 1 -> 2: 4
  - 1 -> 3: 2
  - 1 -> 5: -5
  - 2 -> 4: 2
  - 2 -> 5: 8
  - 3 -> 2: 5
  - 4 -> 1: 3
  - 4 -> 3: 6
  - 5 -> 4: 6

#### Initial Matrix ($D^0$)

We represent this as an adjacency matrix where $\infty$ represents no direct edge.

```math
D^0 = \begin{bmatrix}
0 & 4 & 2 & \infty & -5 \\ 
\newline
\infty & 0 & \infty & 2 & 8 \\
\newline
\infty & 5 & 0 & \infty & \infty \\
\newline
3 & \infty & 6 & 0 & \infty \\
\newline
\infty & \infty & \infty & 6 & 0
\newline
\end{bmatrix}
```

### Floyd-Warshall Iterations

The formula is: $D^k[i][j]=min(D^(k−1)[i][j], D^(k−1)[i][k]+D^(k−1)[k][j])$

#### Iteration $k = 1$ (Intermediate Node 1)

* **Path $4 \to 2$:** 
  $$\min(D^{(0)}[4][2], D^{(0)}[4][1] + D^{(0)}[1][2]) = \min(\infty, 3 + 4) = 7$$

* **Path $4 \to 3$:** 
  $$\min(D^{(0)}[4][3], D^{(0)}[4][1] + D^{(0)}[1][3]) = \min(6, 3 + 2) = 5$$

* **Path $4 \to 5$:** 
  $$\min(D^{(0)}[4][5], D^{(0)}[4][1] + D^{(0)}[1][5]) = \min(\infty, 3 + (-5)) = -2$$

---

#### Iteration $k = 2$ (Intermediate Node 2)

* **Path $1 \to 4$:** 
  $$\min(D^{(1)}[1][4], D^{(1)}[1][2] + D^{(1)}[2][4]) = \min(\infty, 4 + 2) = 6$$

* **Path $3 \to 4$:** 
  $$\min(D^{(1)}[3][4], D^{(1)}[3][2] + D^{(1)}[2][4]) = \min(\infty, 5 + 2) = 7$$

* **Path $3 \to 5$:** 
  $$\min(D^{(1)}[3][5], D^{(1)}[3][2] + D^{(1)}[2][5]) = \min(\infty, 5 + 8) = 13$$

---

#### Iteration $k = 3$ (Intermediate Node 3)

No significant changes lower the current minimums. 
For example, for path $1 \to 2$, the current value is $4$. The alternate path via node 3 yields:
$$D^{(2)}[1][3] + D^{(2)}[3][2] = 2 + 5 = 7$$
Since $4 < 7$, no update is made.

---

#### Iteration $k = 4$ (Intermediate Node 4)

* **Path $2 \to 1$:** 
  $$\min(D^{(3)}[2][1], D^{(3)}[2][4] + D^{(3)}[4][1]) = \min(\infty, 2 + 3) = 5$$

* **Path $2 \to 3$:** 
  $$\min(D^{(3)}[2][3], D^{(3)}[2][4] + D^{(3)}[4][3]) = \min(\infty, 2 + 5) = 7$$

* **Path $2 \to 5$:** 
  $$\min(D^{(3)}[2][5], D^{(3)}[2][4] + D^{(3)}[4][5]) = \min(8, 2 + (-2)) = 0$$

* **Path $3 \to 1$:** 
  $$\min(D^{(3)}[3][1], D^{(3)}[3][4] + D^{(3)}[4][1]) = \min(\infty, 7 + 3) = 10$$

* **Path $3 \to 5$:** 
  $$\min(D^{(3)}[3][5], D^{(3)}[3][4] + D^{(3)}[4][5]) = \min(13, 7 + (-2)) = 5$$

* **Path $5 \to 1$:** 
  $$\min(D^{(3)}[5][1], D^{(3)}[5][4] + D^{(3)}[4][1]) = \min(\infty, 6 + 3) = 9$$

* **Path $5 \to 2$:** 
  $$\min(D^{(3)}[5][2], D^{(3)}[5][4] + D^{(3)}[4][2]) = \min(\infty, 6 + 7) = 13$$

* **Path $5 \to 3$:** 
  $$\min(D^{(3)}[5][3], D^{(3)}[5][4] + D^{(3)}[4][3]) = \min(\infty, 6 + 5) = 11$$

---

#### Iteration $k = 5$ (Intermediate Node 5)

* **Path $1 \to 4$:** 
  $$\min(D^{(4)}[1][4], D^{(4)}[1][5] + D^{(4)}[5][4]) = \min(6, -5 + 6) = 1$$

---

#### Final Distance Matrix $D^{(5)}$

The final matrix contains the shortest path distances calculated between all pairs of nodes:

```math
D^{(5)} = \begin{bmatrix}
0 & 4 & 2 & 1 & -5 \\
5 & 0 & 7 & 2 & 0 \\
10 & 5 & 0 & 7 & 5 \\
3 & 7 & 5 & 0 & -2 \\
9 & 13 & 11 & 6 & 0
\end{bmatrix}
```

#### Shortest Path Example:

The shortest path from Node 1 to Node 4 is 1.

- Path: $1 -> 5 -> 4$
- Cost: $-5 + 6 = 1$

### Implementation

### Python

```python title="floyd-warshall-algorithm.py" file=<rootDir>/public/code/mcs-216/section-1/session-9/1/1.py 

```
### C

```c title="floyd-warshall-algorithm.c" file=<rootDir>/public/code/mcs-216/section-1/session-9/1/1.c 

```
### Rust

```rust title="floyd-warshall-algorithm.rs" file=<rootDir>/public/code/mcs-216/section-1/session-9/1/1.rs

```

## Question 2

### Problem Statement

Apply Floyd-Warshall's algorithm to compute the shortest path for the second graph. Compute the $D^5$ matrix.

<img src="/216-sc1-ss9-2.png" class="mt-5 rounded-xl" />

### Answer

#### Graph Analysis

First, we identify the vertices and the weighted directed edges from the image:

- **Vertices**: $V={1,2,3,4,5}$
- **Edges**:
  - 1 -> 2: weight 3
  - 2 -> 1: weight 4
  - 1 -> 5: weight 9
  - 2 -> 3: weight 15
  - 2 -> 4: weight 5
  - 4 -> 2: weight 7
  - 4 -> 3: weight 5
  - 5 -> 3: weight 16
  - 5 -> 4: weight 8

#### Initial Matrix ($D^0$)

We represent this as an adjacency matrix where $\infty$ represents no direct edge.

$$
D^{(0)} = \begin{bmatrix}
0 & 3 & \infty & \infty & 9 \\
4 & 0 & 15 & 5 & \infty \\
\infty & \infty & 0 & \infty & \infty \\
\infty & 7 & 5 & 0 & \infty \\
\infty & \infty & 16 & 8 & 0
\end{bmatrix}
$$

### Floyd-Warshall Iterations

#### Iteration $k = 1$ (Intermediate Node 1)

We check if going through Node 1 offers a shorter path.

* **Path $2 \to 5$:**  
  $$D^{(0)}[2][1] + D^{(0)}[1][5] = 4 + 9 = 13 \quad (\text{Updates } \infty \to 13)$$

$$
D^{(1)} = \begin{bmatrix}
0 & 3 & \infty & \infty & 9 \\
4 & 0 & 15 & 5 & 13 \\
\infty & \infty & 0 & \infty & \infty \\
\infty & 7 & 5 & 0 & \infty \\
\infty & \infty & 16 & 8 & 0
\end{bmatrix}
$$

---

#### Iteration $k = 2$ (Intermediate Node 2)

We check paths through Node 2.

* **Path $1 \to 3$:**  
  $$D^{(1)}[1][2] + D^{(1)}[2][3] = 3 + 15 = 18$$
* **Path $1 \to 4$:**  
  $$D^{(1)}[1][2] + D^{(1)}[2][4] = 3 + 5 = 8$$
* **Path $4 \to 1$:**  
  $$D^{(1)}[4][2] + D^{(1)}[2][1] = 7 + 4 = 11$$
* **Path $4 \to 5$:**  
  $$D^{(1)}[4][2] + D^{(1)}[2][5] = 7 + 13 = 20$$

$$
D^{(2)} = \begin{bmatrix}
0 & 3 & 18 & 8 & 9 \\
4 & 0 & 15 & 5 & 13 \\
\infty & \infty & 0 & \infty & \infty \\
11 & 7 & 5 & 0 & 20 \\
\infty & \infty & 16 & 8 & 0
\end{bmatrix}
$$

---

#### Iteration $k = 3$ (Intermediate Node 3)

Node 3 has no outgoing edges (Row 3 contains all $\infty$ values except for the diagonal position), meaning no shortest paths can be improved by passing through Node 3.

$$
D^{(3)} = D^{(2)}
$$

---

#### Iteration $k = 4$ (Intermediate Node 4)

We check paths through Node 4.

* **Path $1 \to 3$:**  
  $$\min(18, D^{(3)}[1][4] + D^{(3)}[4][3]) = \min(18, 8 + 5) = 13$$
* **Path $2 \to 3$:**  
  $$\min(15, D^{(3)}[2][4] + D^{(3)}[4][3]) = \min(15, 5 + 5) = 10$$
* **Path $5 \to 1$:**  
  $$\min(\infty, D^{(3)}[5][4] + D^{(3)}[4][1]) = \min(\infty, 8 + 11) = 19$$
* **Path $5 \to 2$:**  
  $$\min(\infty, D^{(3)}[5][4] + D^{(3)}[4][2]) = \min(\infty, 8 + 7) = 15$$
* **Path $5 \to 3$:**  
  $$\min(16, D^{(3)}[5][4] + D^{(3)}[4][3]) = \min(16, 8 + 5) = 13$$

$$
D^{(4)} = \begin{bmatrix}
0 & 3 & 13 & 8 & 9 \\
4 & 0 & 10 & 5 & 13 \\
\infty & \infty & 0 & \infty & \infty \\
11 & 7 & 5 & 0 & 20 \\
19 & 15 & 13 & 8 & 0
\end{bmatrix}
$$

---

#### Iteration $k = 5$ (Intermediate Node 5)

We check paths through Node 5. None of the existing paths are improved by going through Node 5 (e.g., path $1 \to 2$ costs $3$, whereas a path via node 5 would cost $9 + 15 = 24$).

$$
D^{(5)} = D^{(4)}
$$

---

#### Final Matrix $D^{(5)}$ and Shortest Paths

The final matrix $D^{(5)}$ represents the absolute shortest distance between every pair of nodes:

$$
D^{(5)} = \begin{bmatrix}
0 & 3 & 13 & 8 & 9 \\
4 & 0 & 10 & 5 & 13 \\
\infty & \infty & 0 & \infty & \infty \\
11 & 7 & 5 & 0 & 20 \\
19 & 15 & 13 & 8 & 0
\end{bmatrix}
$$

#### Shortest Paths:

* **Shortest path from $V_1 \to V_3$:** 
  * Total Distance: $13$
  * Path Traversed: $1 \to 2 \to 4 \to 3$ (Cost computation: $3 + 5 + 5 = 13$)

* **Shortest path from $V_5 \to V_1$:** 
  * Total Distance: $19$
  * Path Traversed: $5 \to 4 \to 2 \to 1$ (Cost computation: $8 + 7 + 4 = 19$)

### Implementation

### Python

```python title="floyd-warshall-algorithm.py" file=<rootDir>/public/code/mcs-216/section-1/session-9/2/2.py 

```
### C

```c title="floyd-warshall-algorithm.c" file=<rootDir>/public/code/mcs-216/section-1/session-9/2/2.c 

```
### Rust

```rust title="floyd-warshall-algorithm.rs" file=<rootDir>/public/code/mcs-216/section-1/session-9/2/2.rs

```

## Question 3

### Problem Statement

Implement the all-pair shortest path algorithm using different graphs.

### Answer

This algorithm works by iteratively improving the estimate of the shortest path between two nodes by considering every other node as a potential intermediate point.

#### The Algorithm Logic

- Initialize the distance matrix `dist` with the direct edge weights (adjacency matrix).
- Loop through every node `k` (from 0 to V-1) to treat it as an intermediate node.
- For every pair of nodes `(i, j)`, check if the path` i -> k -> j` is shorter than the current known path `i -> j`.
- Update `dist[i][j]` if a shorter path is found.

### Python

```python title="floyd-warshall-algorithm.py" file=<rootDir>/public/code/mcs-216/section-1/session-9/3/3.py 

```
### C

```c title="floyd-warshall-algorithm.c" file=<rootDir>/public/code/mcs-216/section-1/session-9/3/3.c 

```
### Rust

```rust title="floyd-warshall-algorithm.rs" file=<rootDir>/public/code/mcs-216/section-1/session-9/3/3.rs

```

Source: https://syntax.theether.in/mcs-216/section-1/session-9/index.mdx