Session 9

Floyd and Warshall's Algorithm for All Pair Shortest Path Algorithms

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.

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

Algorithm

		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.

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.

D^{0} = [\begin{matrix} 0 & 4 & 2 & \infty & - 5 \\ \infty & 0 & \infty & 2 & 8 \\ \infty & 5 & 0 & \infty & \infty \\ 3 & \infty & 6 & 0 & \infty \\ \infty & \infty & \infty & 6 & 0 \end{matrix}]

Floyd-Warshall Iterations

The formula is: $D^{k} [i] [j] = m i n (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:

D^{(5)} = [\begin{matrix} 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{matrix}]

Shortest Path Example:

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

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

Implementation

Python

floud-warshall-algorithm.py

		# Number of vertices in the graph
V = 5
 
# Define infinity as a large enough value.
INF = 99999
 
 
def floydWarshall(graph):
    """
    Implements the Floyd-Warshall algorithm to find all pairs shortest paths.
    """
    # dist[][] will be the output matrix that will finally have the shortest
    # distances between every pair of vertices
    dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
 
    # Add all vertices one by one to the set of intermediate vertices.
    # k is the intermediate vertex
    for k in range(V):
        # i is the source vertex
        for i in range(V):
            # j is the destination vertex
            for j in range(V):
                # If vertex k is on the shortest path from i to j,
                # then update the value of dist[i][j]
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
 
    print("Shortest distance matrix (D5):")
    for i in range(V):
        for j in range(V):
            if dist[i][j] == INF:
                print("%7s" % ("INF"), end=" ")
            else:
                print("%7d" % (dist[i][j]), end=" ")
        print()
 
 
# Driver program to test the above program
# Mapping: 1->0, 2->1, 3->2, 4->3, 5->4
graph = [
    [0, 4, 2, INF, -5],
    [INF, 0, INF, 2, 8],
    [INF, 5, 0, INF, INF],
    [3, INF, 6, 0, INF],
    [INF, INF, INF, 6, 0],
]
 
floydWarshall(graph)

C Language

floud-warshall-algorithm.c

		#include <stdio.h>
 
#define V 5
#define INF 999999
 
void floydWarshall(int graph[V][V]) {
    int dist[V][V];
    int i, j, k;
 
    // Initialize the solution matrix same as input graph matrix
    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            dist[i][j] = graph[i][j];
 
    /* Add all vertices one by one to the set of intermediate
       vertices.
       ---> Before start of an iteration, we have shortest
            distances between all pairs of vertices such that
            the shortest distances consider only the vertices
            in set {0, 1, 2, .. k-1} as intermediate vertices.
       ----> After the end of an iteration, vertex no. k is
             added to the set of intermediate vertices and the
             set becomes {0, 1, 2, .. k}
    */
    for (k = 0; k < V; k++) {
        // Pick all vertices as source one by one
        for (i = 0; i < V; i++) {
            // Pick all vertices as destination for the
            // above picked source
            for (j = 0; j < V; j++) {
                // If vertex k is on the shortest path from
                // i to j, then update the value of dist[i][j]
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
 
    // Print the shortest distance matrix
    printf("The following matrix shows the shortest distances between every pair of vertices\n");
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            if (dist[i][j] == INF)
                printf("%7s", "INF");
            else
                printf("%7d", dist[i][j]);
        }
        printf("\n");
    }
}
 
int main() {
    /* Let us create the following weighted graph
            1       2       3       4       5
        1   0       4       2       INF    -5
        2   INF     0       INF     2       8
        3   INF     5       0       INF     INF
        4   3       INF     6       0       INF
        5   INF     INF     INF     6       0
    */
    int graph[V][V] = { {0, 4, 2, INF, -5},
                        {INF, 0, INF, 2, 8},
                        {INF, 5, 0, INF, INF},
                        {3, INF, 6, 0, INF},
                        {INF, INF, INF, 6, 0} };
 
    floydWarshall(graph);
    return 0;
}

Rust

floud-warshall-algorithm.rs

		const V: usize = 5;
const INF: i32 = 999999;
 
fn floyd_warshall(graph: &[[i32; V]; V]) {
    // Create a mutable copy of the graph to store distances
    let mut dist = *graph;
 
    // k is the intermediate vertex
    for k in 0..V {
        // i is the source vertex
        for i in 0..V {
            // j is the destination vertex
            for j in 0..V {
                // If vertex k is on the shortest path from i to j,
                // then update the value of dist[i][j]
                // We check for INF to prevent overflow, though with these values it's unlikely
                if dist[i][k] != INF && dist[k][j] != INF {
                    if dist[i][k] + dist[k][j] < dist[i][j] {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
    }
 
    println!("The following matrix shows the shortest distances between every pair of vertices:");
    for i in 0..V {
        for j in 0..V {
            if dist[i][j] == INF {
                print!("{:>7} ", "INF");
            } else {
                print!("{:>7} ", dist[i][j]);
            }
        }
        println!();
    }
}
 
fn main() {
    /*
       Graph representation (0-indexed):
       Node 1 -> index 0
       Node 2 -> index 1
       ...
    */
    let graph: [[i32; V]; V] = [
        [0, 4, 2, INF, -5],
        [INF, 0, INF, 2, 8],
        [INF, 5, 0, INF, INF],
        [3, INF, 6, 0, INF],
        [INF, INF, INF, 6, 0],
    ];
 
    floyd_warshall(&graph);
}

Question 2

Problem Statement

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

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{matrix} 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{matrix}]

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 (Updates \infty \to 13)$

D^{(1)} = [\begin{matrix} 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{matrix}]

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{matrix} 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{matrix}]

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{matrix} 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{matrix}]

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{matrix} 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{matrix}]

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

floud-warshall-algorithm.py

		# Number of vertices in the graph
V = 5
 
# Define infinity as a large enough value.
INF = 99999
 
 
def floydWarshall(graph):
    """
    Implements the Floyd-Warshall algorithm to find all pairs shortest paths.
    """
    # dist[][] will be the output matrix that will finally have the shortest
    # distances between every pair of vertices
    dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
 
    # Add all vertices one by one to the set of intermediate vertices.
    # k is the intermediate vertex
    for k in range(V):
        # i is the source vertex
        for i in range(V):
            # j is the destination vertex
            for j in range(V):
                # If vertex k is on the shortest path from i to j,
                # then update the value of dist[i][j]
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
 
    print("Shortest distance matrix (D5):")
    for i in range(V):
        for j in range(V):
            if dist[i][j] == INF:
                print("%7s" % ("INF"), end=" ")
            else:
                print("%7d" % (dist[i][j]), end=" ")
        print()
 
 
# Driver program to test the above program
# Mapping: V1->0, V2->1, V3->2, V4->3, V5->4
graph = [
    [0, 3, INF, INF, 9],
    [4, 0, 15, 5, INF],
    [INF, INF, 0, INF, INF],
    [INF, 7, 5, 0, INF],
    [INF, INF, 16, 8, 0],
]
 
floydWarshall(graph)

C Language

floud-warshall-algorithm.c

		#include <stdio.h>
 
#define V 5
#define INF 999999
 
void floydWarshall(int graph[V][V]) {
    int dist[V][V];
    int i, j, k;
 
    // Initialize the solution matrix same as input graph matrix
    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            dist[i][j] = graph[i][j];
 
    /* Add all vertices one by one to the set of intermediate
       vertices.
       ---> Before start of an iteration, we have shortest
            distances between all pairs of vertices such that
            the shortest distances consider only the vertices
            in set {0, 1, 2, .. k-1} as intermediate vertices.
       ----> After the end of an iteration, vertex no. k is
             added to the set of intermediate vertices and the
             set becomes {0, 1, 2, .. k}
    */
    for (k = 0; k < V; k++) {
        // Pick all vertices as source one by one
        for (i = 0; i < V; i++) {
            // Pick all vertices as destination for the
            // above picked source
            for (j = 0; j < V; j++) {
                // If vertex k is on the shortest path from
                // i to j, then update the value of dist[i][j]
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
 
    // Print the shortest distance matrix
    printf("The following matrix shows the shortest distances between every pair of vertices (D5):\n");
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            if (dist[i][j] == INF)
                printf("%7s", "INF");
            else
                printf("%7d", dist[i][j]);
        }
        printf("\n");
    }
}
 
int main() {
    /* Let us create the following weighted graph
       Mapping: V1=0, V2=1, V3=2, V4=3, V5=4
 
            V1      V2      V3      V4      V5
        V1   0       3       INF     INF     9
        V2   4       0       15      5       INF
        V3   INF     INF     0       INF     INF
        V4   INF     7       5       0       INF
        V5   INF     INF     16      8       0
    */
    int graph[V][V] = { {0, 3, INF, INF, 9},
                        {4, 0, 15, 5, INF},
                        {INF, INF, 0, INF, INF},
                        {INF, 7, 5, 0, INF},
                        {INF, INF, 16, 8, 0} };
 
    floydWarshall(graph);
    return 0;
}

Rust

floud-warshall-algorithm.rs

		const V: usize = 5;
const INF: i32 = 999999;
 
fn floyd_warshall(graph: &[[i32; V]; V]) {
    // Create a mutable copy of the graph to store distances
    let mut dist = *graph;
 
    // k is the intermediate vertex
    for k in 0..V {
        // i is the source vertex
        for i in 0..V {
            // j is the destination vertex
            for j in 0..V {
                // If vertex k is on the shortest path from i to j,
                // then update the value of dist[i][j]
                // We check for INF to prevent overflow
                if dist[i][k] != INF && dist[k][j] != INF {
                    if dist[i][k] + dist[k][j] < dist[i][j] {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
    }
 
    println!(
        "The following matrix shows the shortest distances between every pair of vertices (D5):"
    );
    for i in 0..V {
        for j in 0..V {
            if dist[i][j] == INF {
                print!("{:>7} ", "INF");
            } else {
                print!("{:>7} ", dist[i][j]);
            }
        }
        println!();
    }
}
 
fn main() {
    /*
       Graph representation (0-indexed):
       V1 -> index 0
       V2 -> index 1
       V3 -> index 2
       V4 -> index 3
       V5 -> index 4
    */
    let graph: [[i32; V]; V] = [
        [0, 3, INF, INF, 9],
        [4, 0, 15, 5, INF],
        [INF, INF, 0, INF, INF],
        [INF, 7, 5, 0, INF],
        [INF, INF, 16, 8, 0],
    ];
 
    floyd_warshall(&graph);
}

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

floud-warshall-algorithm.py

		# Number of vertices in the graph
V = 5
 
 
def floydWarshall(graph):
    """
    Implements the Floyd-Warshall algorithm to find all pairs shortest paths.
    """
    # dist[][] will be the output matrix that will finally have the shortest
    # distances between every pair of vertices.
    # We create a deep copy to avoid modifying the original graph structure.
    dist = [row[:] for row in graph]
 
    # Add all vertices one by one to the set of intermediate vertices.
    # k is the intermediate vertex
    for k in range(V):
        # i is the source vertex
        for i in range(V):
            # j is the destination vertex
            for j in range(V):
                # If vertex k is on the shortest path from i to j,
                # then update the value of dist[i][j]
                # We check if dist[i][k] and dist[k][j] are not infinity
                if dist[i][k] != float("inf") and dist[k][j] != float("inf"):
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
 
    print("Shortest distance matrix (D5):")
    for i in range(V):
        for j in range(V):
            if dist[i][j] == float("inf"):
                print("%7s" % ("INF"), end=" ")
            else:
                print("%7d" % (dist[i][j]), end=" ")
        print()
 
 
# Driver program to test the above program
# Mapping: V1->0, V2->1, V3->2, V4->3, V5->4
graph = [
    [0, 3, float("inf"), float("inf"), 9],
    [4, 0, 15, 5, float("inf")],
    [float("inf"), float("inf"), 0, float("inf"), float("inf")],
    [float("inf"), 7, 5, 0, float("inf")],
    [float("inf"), float("inf"), 16, 8, 0],
]
 
floydWarshall(graph)

C Language

floud-warshall-algorithm.c

		#include <stdio.h>
 
// Define the number of vertices
#define V 5
// Define Infinity (a value larger than any possible path sum)
#define INF 99999
 
void floydWarshall(int graph[V][V]) {
    // dist[i][j] will store the shortest distance from i to j
    int dist[V][V];
    int i, j, k;
 
    // 1. Initialize the solution matrix same as input graph matrix
    //    Or we can say the initial values of shortest distances are based
    //    on shortest paths considering no intermediate vertices.
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
        }
    }
 
    // 2. Add all vertices one by one to the set of intermediate vertices.
    //    k is the intermediate vertex.
    for (k = 0; k < V; k++) {
        // i is the source vertex
        for (i = 0; i < V; i++) {
            // j is the destination vertex
            for (j = 0; j < V; j++) {
                // If vertex k is on the shortest path from i to j,
                // then update the value of dist[i][j]
                // Check for INF to prevent integer overflow
                if (dist[i][k] != INF && dist[k][j] != INF &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
 
    // Print the shortest distance matrix
    printf("The following matrix shows the shortest distances between every pair of vertices:\n");
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            if (dist[i][j] == INF)
                printf("%7s", "INF");
            else
                printf("%7d", dist[i][j]);
        }
        printf("\n");
    }
}
 
int main() {
    /*
       Example Graph (Based on the second image provided previously):
       Mapping: V1=0, V2=1, V3=2, V4=3, V5=4
 
       Edges:
       1->2 (3), 1->5 (9)
       2->1 (4), 2->3 (15), 2->4 (5)
       4->2 (7), 4->3 (5)
       5->3 (16), 5->4 (8)
    */
    int graph[V][V] = {
        {0,   3,  INF, INF, 9},
        {4,   0,  15,  5,   INF},
        {INF, INF, 0,   INF, INF},
        {INF, 7,  5,   0,   INF},
        {INF, INF, 16,  8,   0}
    };
 
    floydWarshall(graph);
    return 0;
}

Rust

floud-warshall-algorithm.rs

		const V: usize = 5;
const INF: i32 = 999999;
 
fn floyd_warshall(graph: &[[i32; V]; V]) {
    // Create a mutable copy of the graph to store distances.
    // In Rust, arguments are immutable by default, so we clone it.
    let mut dist = *graph;
 
    // k is the intermediate vertex
    for k in 0..V {
        // i is the source vertex
        for i in 0..V {
            // j is the destination vertex
            for j in 0..V {
                // If vertex k is on the shortest path from i to j,
                // then update the value of dist[i][j]
 
                // Check for INF to prevent integer overflow during addition
                if dist[i][k] != INF && dist[k][j] != INF {
                    if dist[i][k] + dist[k][j] < dist[i][j] {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
    }
 
    println!("The following matrix shows the shortest distances between every pair of vertices:");
    for i in 0..V {
        for j in 0..V {
            if dist[i][j] == INF {
                print!("{:>7} ", "INF");
            } else {
                print!("{:>7} ", dist[i][j]);
            }
        }
        println!();
    }
}
 
fn main() {
    /*
       Graph representation (0-indexed):
       V1 -> index 0
       V2 -> index 1
       V3 -> index 2
       V4 -> index 3
       V5 -> index 4
    */
    let graph: [[i32; V]; V] = [
        [0, 3, INF, INF, 9],
        [4, 0, 15, 5, INF],
        [INF, INF, 0, INF, INF],
        [INF, 7, 5, 0, INF],
        [INF, INF, 16, 8, 0],
    ];
 
    floyd_warshall(&graph);
}

Session 8

Implementation of Binomial Coefficient Algorithm

Session 10

Chained Matrix Multiplication

Session 9

Objectives

Concept

Algorithm

Complexity

Question 1

Problem Statement

Answer

Graph Analysis

Initial Matrix (D0)

Floyd-Warshall Iterations

Iteration k=1 (Intermediate Node 1)

Iteration k=2 (Intermediate Node 2)

Iteration k=3 (Intermediate Node 3)

Iteration k=4 (Intermediate Node 4)

Iteration k=5 (Intermediate Node 5)

Final Distance Matrix D(5)

Shortest Path Example:

Implementation

Python

C Language

Rust

Question 2

Problem Statement

Answer

Graph Analysis

Initial Matrix (D0)

Floyd-Warshall Iterations

Iteration k=1 (Intermediate Node 1)

Iteration k=2 (Intermediate Node 2)

Iteration k=3 (Intermediate Node 3)

Iteration k=4 (Intermediate Node 4)

Iteration k=5 (Intermediate Node 5)

Final Matrix D(5) and Shortest Paths

Shortest Paths:

Implementation

Python

C Language

Rust

Question 3

Problem Statement

Answer

The Algorithm Logic

Python

C Language

Rust

Initial Matrix ( $D^{0}$ )

Iteration $k = 1$ (Intermediate Node 1)

Iteration $k = 2$ (Intermediate Node 2)

Iteration $k = 3$ (Intermediate Node 3)

Iteration $k = 4$ (Intermediate Node 4)

Iteration $k = 5$ (Intermediate Node 5)

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

Initial Matrix ( $D^{0}$ )

Iteration $k = 1$ (Intermediate Node 1)

Iteration $k = 2$ (Intermediate Node 2)

Iteration $k = 3$ (Intermediate Node 3)

Iteration $k = 4$ (Intermediate Node 4)

Iteration $k = 5$ (Intermediate Node 5)

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