Floyd Warshall Algorithm With Example

by

The Floyd-Warshall algorithm is an algorithm that is used to find the shortest paths between all pairs of vertices in a weighted graph. This graph can be either directed or undirected. And the weights of the edges between two vertices can be positive, negative, or zero. However, the graph must not contain any negative weight cycles (cycles in the graph where the total weight is negative).

Floyd-Warshall algorithm basically follow the dynamic programming approach. It checks every possible path between the two vertices/nodes to calculate shortest distance between every pair of vertices/nodes.

Robert Floyd and Stephen Warshall created this algorithm. It’s very useful for things like GPS systems to find the best routes. It’s also used in computer networks to manage data flow. It helps to find the quickest way from one point to another.

Imagine you have a map of a few cities and the distances between them. This algorithm would look at all possible routes to find the shortest one between each pair of cities.

How Floyd Warshall Algorithm Work?

  1. Starting Off: We begin with a special table that shows how the points, or ‘vertices,’ ,’nodes’ in a graph are connected. If there is a direct path between two points, the table shows how long it is i.e. we put the value of the edge weight. If there isn’t a direct path, then we will put the really big number like infinite. And for the self vertices we put the 0.
  2. Making Updates: The algorithm checks every pair of points and tries to find if there’s a shorter path between them by going through another point. This process is repeated to make sure we find the shortest paths.
  3. Finishing Up: After checking all possible paths, the table will have the shortest distances between all the points.

Floyd Warshall Pseudocode

function FloydWarshall(graph):
    let dist be a |V| × |V| array of minimum distances initialized to Infinity
    for each vertex v
        dist[v][v] := 0
    for each edge (u,v)
        dist[u][v] := weight(u, v)
    for k from 1 to |V|
        for i from 1 to |V|
            for j from 1 to |V|
                if dist[i][k] + dist[k][j] < dist[i][j]
                    dist[i][j] := dist[i][k] + dist[k][j]
    return dist

Algorithm Steps

  1. Initialize: Start with the given matrix.
  2. Iterate for Each Vertex k: For each pair of vertices (i, j), update dist[i][j] to min(dist[i][j], dist[i][k] + dist[k][j])

Example to understand Floyd Warshall Algorithm

Suppose we have a directed graph with four vertices (0, 1, 2, 3) and the following weighted edges:

Floyd Warshall Algorithm
  • Edge from 0 to 1 with weight 3
  • Edge from 0 to 3 with weight 7
  • Edge from 1 to 0 with weight 8
  • Edge from 1 to 2 with weight 2
  • Edge from 2 to 1 with weight 5
  • Edge from 2 to 3 with weight 1
  • Edge from 3 to 0 with weight 2

The graph’s adjacency matrix looks like this (using ∞ to represent no direct edge):

For Vertex 0

Using Vertex 0 as Intermediate:

  • Evaluate paths through Vertex 0.
  • Update dist[i][j] to min(dist[i][j], dist[i][0] + dist[0][j]).
  • For self node, value will be 0.
0123
003∞7
180∞15
2∞808
325∞0

For Vertex 1

In the above steps we have calculated the path from vertex 0. Now in this step we are checking if there is some shortest path if we consider vertex 1 as an intermediate vertex.

We’ll update each dist[i][j] to min(dist[i][j], dist[i][1] + dist[1][j]) for all pairs of vertices (i, j).

Given the current state of the matrix:

0123
003∞7
180∞15
2∞808
325∞0

Using Vertex 1 as Intermediate:

Each element of the matrix will be updated based on whether the path through Vertex 1 gives a shorter path between the pair of vertices:

  1. Update for dist[0][2]:
    • Current value of dist[0][2] is ∞.
    • dist[0][1] + dist[1][2] is 3 + 2 = 5.
    • Update dist[0][2] to min(∞, 5), which is 5.
  2. Update for dist[0][3]:
    • Current value of dist[0][3] is 7.
    • dist[0][1] + dist[1][3] is 3 + ∞ = ∞.
    • Update dist[0][3] to min(7, ∞), which is 7.
  3. Update for dist[2][0]:
    • Current value of dist[2][0] is ∞.
    • dist[2][1] + dist[1][0] is 5 + 8 = 13.
    • Update dist[2][0] to min(∞, 13), which is 13.
  4. Update for dist[2][3]:
    • Current value of dist[2][3] is 1.
    • dist[2][1] + dist[1][3] is 5 + ∞ = ∞.
    • Update dist[2][3] to min(1, ∞), which is 1.
  5. Update for dist[3][0]:
    • Current value of dist[3][0] is 2.
    • dist[3][1] + dist[1][0] is ∞ + 8 = ∞.
    • Update dist[3][0] to min(2, ∞), which is 2.
  6. Update for dist[3][2]:
    • Current value of dist[3][2] is ∞.
    • dist[3][1] + dist[1][2] is ∞ + 2 = ∞.
    • Update dist[3][2] to min(∞, ∞), which remains ∞.

Updated Matrix after applying above operation

After applying these updates using Vertex 1 as an intermediate vertex, the matrix becomes:

0123
00357
1802∞
213501
32∞∞0

This matrix now contains updated shortest path distances between all pairs of vertices when considering vertex 1 as an intermediate step in the paths.

For Vertex 2

In the above steps we have calculated the path by consider vertex 1 as an intermediate vertex. Now in this step we are considering vertex 2 as intermediate and checking if there is possible shortest path.

We’ll calculate min(dist[i][j], dist[i][2] + dist[2][j]) for each pair of vertices (i, j).

Given the current state of the matrix:

0123
00357
1802∞
213501
32∞∞0

Using Vertex 2 as Intermediate

  1. Update for dist[0][3]:
    • Current value: dist[0][3] = 7.
    • New possible value: dist[0][2] + dist[2][3] = 5 + 1 = 6.
    • Update: dist[0][3] = min(7, 6) = 6.
  2. Update for dist[1][0]:
    • Current value: dist[1][0] = 8.
    • New possible value: dist[1][2] + dist[2][0] = 2 + 13 = 15.
    • No update needed since 8 < 15.
  3. Update for dist[1][3]:
    • Current value: dist[1][3] = ∞.
    • New possible value: dist[1][2] + dist[2][3] = 2 + 1 = 3.
    • Update: dist[1][3] = min(∞, 3) = 3.
  4. Update for dist[3][0]:
    • Current value: dist[3][0] = 2.
    • New possible value: dist[3][2] + dist[2][0] = 7 + 13 = 20.
    • No update needed since 2 < 20.
  5. Update for dist[3][1]:
    • Current value: dist[3][1] = ∞.
    • New possible value: dist[3][2] + dist[2][1] = 7 + 5 = 12.
    • Update: dist[3][1] = min(∞, 12) = 12.

Updated Matrix after applying above operation

After applying these updates using Vertex 2 as an intermediate vertex, the matrix becomes:

0123
00356
18023
213501
321270

This matrix now reflects the shortest path distances between all pairs of vertices when considering vertex 2 as an intermediate step in the paths. The value of dist[i][j] represents the shortest distance from vertex i to vertex j after incorporating paths that pass through vertex 2.

For Vertex 3

In the above steps we have calculated the path by consider vertex 2 as an intermediate vertex. Now in this step we are considering vertex 3 as intermediate and checking if there is possible shortest path.

We’ll calculate min(dist[i][j], dist[i][3] + dist[3][j]) for each pair of vertices (i, j).

Given the current state of the matrix:

0123
00356
15023
24501
32560

Using Vertex 3 as Intermediate

  1. Update for dist[0][1]:
    • Current value: dist[0][1] = 3.
    • New possible value: dist[0][3] + dist[3][1] = 6 + 5 = 11.
    • No update needed since 3 < 11.
  2. Update for dist[0][2]:
    • Current value: dist[0][2] = 5.
    • New possible value: dist[0][3] + dist[3][2] = 6 + 6 = 12.
    • No update needed since 5 < 12.
  3. Update for dist[1][0]:
    • Current value: dist[1][0] = 5.
    • New possible value: dist[1][3] + dist[3][0] = 3 + 2 = 5.
    • No update needed since they are equal.
  4. Update for dist[1][2]:
    • Current value: dist[1][2] = 2.
    • New possible value: dist[1][3] + dist[3][2] = 3 + 6 = 9.
    • No update needed since 2 < 9.
  5. Update for dist[2][0]:
    • Current value: dist[2][0] = 4.
    • New possible value: dist[2][3] + dist[3][0] = 1 + 2 = 3.
    • Update: dist[2][0] = min(4, 3) = 3.
  6. Update for dist[2][1]:
    • Current value: dist[2][1] = 5.
    • New possible value: dist[2][3] + dist[3][1] = 1 + 5 = 6.
    • No update needed since 5 < 6.

Updated Matrix after applying above operation

After applying these updates using Vertex 3 as an intermediate vertex, the matrix becomes:

0123
00356
15023
23501
32560

This matrix now represents the shortest path distances between all pairs of vertices when considering vertex 3 as an intermediate step in the paths. The value of dist[i][j] represents the shortest distance from vertex i to vertex j after incorporating paths that pass through vertex 3.