Session 9

This session (PDF)MCS-216 Section 1 (ZIP)MCS-216 (ZIP)Semester 1 (ZIP)

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

Do not copy. Read for understanding and the viva

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

Concept

Do not copy. Read for understanding and the viva

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

Write in lab record

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

Do not copy. Read for understanding and the viva

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

Question 1

Problem Statement

Write in lab record

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

Answer

Write in lab record

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

Graph Analysis

Do not copy. Read for understanding and the viva

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

Write in lab record

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

Write in lab record

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)

Write in lab record

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)

Write in lab record

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)

Write in lab record

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)

Write in lab record

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)

Write in lab record

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

Write in lab record

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:

Write in lab record

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

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

Implementation

Write in lab record

Lab record: write one language only. Pick yours once and every page opens on it; the other tabs are the same solution for comparison.Your language

floyd-warshall-algorithm.pypython

# 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)

floyd-warshall-algorithm.cc

#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;
}

floyd-warshall-algorithm.rsrust

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

Write in lab record

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

Answer

Write in lab record

Graph Analysis

Do not copy. Read for understanding and the viva

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

Write in lab record

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

Write in lab record

Iteration $k = 1$ (Intermediate Node 1)

Write in lab record

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)

Write in lab record

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)

Write in lab record

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)

Write in lab record

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)

Write in lab record

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

Write in lab record

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:

Write in lab record

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

Write in lab record

Lab record: write one language only. Pick yours once and every page opens on it; the other tabs are the same solution for comparison.Your language

floyd-warshall-algorithm.pypython

# 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)

floyd-warshall-algorithm.cc

#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;
}

floyd-warshall-algorithm.rsrust

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

Write in lab record

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

Answer

Write in lab record

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

Do not copy. Read for understanding and the viva

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.

Lab record: write one language only. Pick yours once and every page opens on it; the other tabs are the same solution for comparison.Your language

floyd-warshall-algorithm.pypython

# 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)

floyd-warshall-algorithm.cc

#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;
}

floyd-warshall-algorithm.rsrust

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);
}

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

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

Question 3

Problem Statement

Answer

The Algorithm Logic

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