Floyd-Warshall Shortest Path Algorithm

Below are some of the key points of Floyd-Warshall’s shortest path for all node pairs

  • Floyd-Warshall algorithm finds the shortest path between all pairs of vertices (in terms of distance / cost ) in a directed weighted graph containing positive and negative edge weights.
  • This algorithm works on graphs without any negative weight cycles.
  • This algorithm uses a recursive function Shortest_Path ( i, j, k ), where i is the source, j is the destination and [ 1…k ] are the intermediate nodes that can be used for going from i to j.
    Thus,
    Shortest_Path ( i, j, k ) = Minimum ( Shortest_Path ( i, j, k-1 ) , Shortest_Path ( i, k, k-1 ) + Shortest_Path ( k, j, k-1 ) )
    Where,
    The shortest path does not visit an intermediate node k
    Shortest_Path ( i, j, k-1 )  : The shortest path from i to j does not take an intermediate node k but there are still ( k-1 ) nodes to choose from.
    The shortest path visits an intermediate node k
    Shortest_Path ( i, k, k-1 ) : The shortest path from i to k with intermediate nodes ( k-1 ) to choose from.
    Shortest_Path ( k, j, k-1 ) : The shortest path from k to j with intermediate nodes ( k-1 ) to choose from.
    Using this recursive function as a base, the Floyd-Warshall finds the shortest path from node i to node j using all the available intermediate nodes [ 1 … k ].

Floyd_Warshall

Algorithm : Floyd-Warshall

1.    Create a two-dimensional array of size n x n for storing the length of the shortest path between all node pairs.
      n is the number of nodes in the graph.
      Initialize all the cells of this array with ∞.
2.    For every node i in the graph, initialize the distance of the node to itself as 0.
           Distance [ i ] [ i ] = 0.
3.    For every edge ( u, v ) in the graph, initialize the distance array as the weight of the edge.
           Distance [ u ] [ v ] = Weight of (u, v)
4.    For every node k in [ 1 … n ] do
          For every node i in [ 1 … n ] do
              For every node j in [ 1 … n ] do
                   If ( Distance [ i ] [ j ] > Distance [ i ] [ k ] + Distance [ k ] [ j ] ) :
                      Distance [ i ] [ j ] = Distance [ i ] [ k ] + Distance [ k ] [ j ]

Floyd-Warshall path construction example

Consider the shortest path in terms of weight / distance between node Source ( 1 ) - Destination ( 3 ) : [ 1 2 3 ]
Case 1 : The shortest path from a node to itself is the node itself. i.e next [ i ] [ i ] = i.
Example : next [ 1 ] [ 1 ] = 1 i.e Next node from 1 to reach 1 is 1.
Example : next [ 3 ] [ 3 ] = 3 i.e Next node from 3 to reach 3 is 3.
Case 2 : If the shortest path from node i to node j does not visit any intermediate node, next [ i ] [ j ] = j.
Example : next [ 1 ] [ 2 ] = 2 i.e Next node from 1 to reach 2 is 2.
Example : next [ 2 ] [ 3 ] = 3 i.e Next node from 2 to reach 3 is 3.
Case 3 : If the shortest path from node i to node j visits an intermediate node k, next [ i ] [ j ] = next [ i ] [ k ]
Example : next [ 1 ] [ 3 ] = next [ 1 ] [ 2 ] = 2 i.e Next node from 1 to 3 is 2.

To construct the path from Source 1 - Destination 3 the algorithm follows the below steps

  1. Insert source node 1 in the path [ 1 ]
  2. Find the next node in the path from 1 - 3 i.e next [ 1 ] [ 3 ] = 2. Insert node 2 in the path [ 1 2 ]. 2 becomes the source node.
  3. Find the next node in the path from 2 - 3 i.e next [ 2 ] [ 3 ] = 3. Insert node 3 in the path [ 1 2 3 ]. 3 becomes the source which is now same as the destination.

Algorithm : Path construction ( Source src, Destination dst )

1.     If next [ src ] [ dst ] == -1 then no path exist.
           return empty path [ ].
2.     Insert path = [ src ]
3.     While ( src != dst )
4.         source = next [ src ] [ dst ]
5.         Append src to path

Floyd_Warshall_All_Pairs_Shortest_Path

Graph type : Designed for directed weighted graphs containing positive and negative edge weights and no negative weight cycles.
Data structure used for storing graph : Edge list for storing the edges and their corresponding weights.
Time complexity : O ( N 3 ). N is the number of vertices / node in the graph.

Floyd-Warshall’s all pairs shortest path implementation. 

#  Example : Graph 
#         1 
#        /|\
#       / | \
#     9/  |7 \3
#     / 3 |   \
#    0----4----2
#     \   | 1 /
#     2\  |1 /-2
#       \ | /
#        \|/
#         3 
#
class Edge :

    def __init__(self, src, dst, weight) :
        self.src = src
        self.dst = dst
        self.weight = weight

class Graph:

    def __init__(self, arg_nodes):

        self.nodes = arg_nodes
        # Edge weight is a dictionary for storing the weight of the edges { "src-dst" : weight }
        self.edge_list = []        
        # distance is a 2-dimensional array that stores the shortest distance between [src][dst]
        self.distance = [999999999] * arg_nodes
        # next is a 2-dimensional array that stores the node next to the source. This is used
        # for path construction between [src][dst] 
        self.next = [-1] * arg_nodes

        for i in range(arg_nodes):
            self.distance[i] = [999999999] * arg_nodes
            self.next[i] = [-1] * arg_nodes
    
    def AddEdge (self, src, dst, weight, isbidirectional = True):
        e = Edge(src, dst, weight)
        self.edge_list.append(e)
        if (isbidirectional):
            e = Edge(dst, src, weight)
            self.edge_list.append(e)
            
    def Floyd_Warshall(self):

        for i in range (self.nodes):
            self.distance[i][i] = 0
            self.next[i][i] = i

        for edge in self.edge_list:
            weight = edge.weight
            u = edge.src
            v = edge.dst
            self.distance[u][v] = weight
            self.next[u][v] = v


        for k in range(self.nodes):
            for i in range(self.nodes):
                for j in range(self.nodes):
                    if (self.distance[i][j] > self.distance[i][k] + self.distance[k][j]):
                        self.distance[i][j] = self.distance[i][k] + self.distance[k][j]
                        self.next[i][j] = self.next[i][k]

        print("Shortest distance between nodes\n")
        for u in range(self.nodes):
            for v in range(u+1, self.nodes):
                print("Distance ( " + str(u) + " - " + str(v) + " ) : " + str(self.distance[u][v]))
                self.PathConstruction(u, v)
            
    # Construct path from source node to destination node
    def PathConstruction (self, src, dst):

        print("# Path between " + str(src) + " and " + str(dst) + " : ", end = ' ')

        if (self.next[src][dst] == -1):
            print("No path exists")
        else:
            path = []
            path.append(src)

            while (src != dst):
                src = self.next[src][dst]
                path.append(src)

            for node in path:
                print(str(node) + " ", end = ' ')
            print("\n")
            
def main():

    g = Graph(5)

    # Edges from node 0
    g.AddEdge(0, 1, 9)
    g.AddEdge(0, 3, 2)
    g.AddEdge(0, 4, 3)

    # Edges from node 1
    g.AddEdge(1, 2, 3)
    g.AddEdge(1, 4, 7)

    # Edges from node 2
    # Edge from 2 -> 3 is unidirectional. If it was bidirectional, it would introduce negative weight cycle
    # causing the Floyd-Warshall algorithm to fail.
    g.AddEdge(2, 3, -2, False)
    g.AddEdge(2, 4, 1)

    # Edges from node 3
    g.AddEdge(3, 4, 1)

    g.Floyd_Warshall()

if __name__ == "__main__":
    main()

Output

Shortest distance between nodes

Distance ( 0 - 1 ) : 7
# Path between 0 and 1 :  0  4  2  1  

Distance ( 0 - 2 ) : 4
# Path between 0 and 2 :  0  4  2  

Distance ( 0 - 3 ) : 2
# Path between 0 and 3 :  0  3  

Distance ( 0 - 4 ) : 3
# Path between 0 and 4 :  0  4  

Distance ( 1 - 2 ) : 3
# Path between 1 and 2 :  1  2  

Distance ( 1 - 3 ) : 1
# Path between 1 and 3 :  1  2  3  

Distance ( 1 - 4 ) : 2
# Path between 1 and 4 :  1  2  3  4  

Distance ( 2 - 3 ) : -2
# Path between 2 and 3 :  2  3  

Distance ( 2 - 4 ) : -1
# Path between 2 and 4 :  2  3  4  

Distance ( 3 - 4 ) : 1
# Path between 3 and 4 :  3  4  


#include<iostream>
#include<list>
#include<vector>

using namespace std;

/*
         1 
        /|\
       / | \
     9/  |7 \3
     / 3 |   \
    0----4----2
     \   | 1 /
     2\  |1 /-2
       \ | /
        \|/
         3 
*/

class Edge {

    public:
        int src;
        int dst;
        int weight;
        Edge () {}
        Edge (int src, int dst, int weight) {
            this->src = src;
            this->dst = dst;
            this->weight = weight;
        }
};

class Graph {

    private:
        list<Edge> edge_list;
        int nodes;
        // distance is a 2-dimensional array that stores the shortest distance between [src][dst]
        vector<vector<int>> distance;
        // next is a 2-dimensional array that stores the node next to the source. This is used
        // for path construction between [src][dst] 
        vector<vector<int>> next;

    public:

        Graph() {}

        Graph (int n) {
            nodes = n;
            distance.resize(n);
            next.resize(n);

            for (int i=0; i<n; i++) {
                distance[i].resize(n, 999999999); // 999999999 indicates infinite distance
                next[i].resize(n, -1);
            }
        }

        void AddEdge (int src, int dst, int weight, bool isbidirectional) {
            Edge e(src, dst, weight);
            edge_list.push_back(e);
            if (isbidirectional) {
                Edge e(dst, src, weight);
                edge_list.push_back(e);
            }
        }

        void Floyd_Warshall() {

            for (int i=0; i<nodes; i++) {
                distance[i][i] = 0;
                next[i][i] = i;
            }

            for (auto edge : edge_list) {
                int u = edge.src;
                int v = edge.dst;
                distance[u][v] = edge.weight;
                next[u][v] = v;
            }

            for (int k=0; k<nodes; k++) {
                for (int i=0; i<nodes; i++) {
                    for (int j=0; j<nodes; j++) {
                        if (distance[i][j] > distance[i][k] + distance[k][j]) {
                            distance[i][j] = distance[i][k] + distance[k][j];
                            next[i][j] = next[i][k];
                        }
                    }
                }
            }

            cout << "Shortest distance between nodes" << endl;
            for (int u=0; u<nodes; u++) {
                for (int v=u+1; v<nodes; v++) {
                    cout << "\nDistance ( " << u << " - " << v << " ) : " << distance[u][v] << endl;
                    PathConstruction(u, v);
                }
            }
        }

        // Construct path from source node to destination node
        void PathConstruction (int src, int dst) {

            cout << "# Path between " << src << " and " << dst << " : ";

            if (next[src][dst] == -1) {
               cout << "No path exists" << endl;
            } else {
               vector<int> path;
               path.push_back(src);

               while (src != dst) {
                   src = next[src][dst];
                   path.push_back(src);
               }

               for (auto& it : path)
                   cout << it << " ";
               cout << endl;
            }
        }
};

int main() {

    Graph g(5);

    // Edges from node 0
    // AddEdge(src, dst, weight, bi-directional(true/false))  
    g.AddEdge(0, 1, 9, true);
    g.AddEdge(0, 3, 2, true);
    g.AddEdge(0, 4, 3, true);

    // Edges from node 1
    g.AddEdge(1, 2, 3, true);
    g.AddEdge(1, 4, 7, true);

    // Edges from node 2
    // Edge from 2 -> 3 is unidirectional. If it was bidirectional, it would introduce negative weight cycle
    // causing the Floyd-Warshall algorithm to fail.
    g.AddEdge(2, 3, -2, false);
    g.AddEdge(2, 4, 1, true);

    // Edges from node 3
    g.AddEdge(3, 4, 1, true);

    g.Floyd_Warshall();

    return 0;
}

Output

Shortest distance between nodes

Distance ( 0 - 1 ) : 7
# Path between 0 and 1 : 0 4 2 1 

Distance ( 0 - 2 ) : 4
# Path between 0 and 2 : 0 4 2 

Distance ( 0 - 3 ) : 2
# Path between 0 and 3 : 0 3 

Distance ( 0 - 4 ) : 3
# Path between 0 and 4 : 0 4 

Distance ( 1 - 2 ) : 3
# Path between 1 and 2 : 1 2 

Distance ( 1 - 3 ) : 1
# Path between 1 and 3 : 1 2 3 

Distance ( 1 - 4 ) : 2
# Path between 1 and 4 : 1 2 3 4 

Distance ( 2 - 3 ) : -2
# Path between 2 and 3 : 2 3 

Distance ( 2 - 4 ) : -1
# Path between 2 and 4 : 2 3 4 

Distance ( 3 - 4 ) : 1
# Path between 3 and 4 : 3 4 


import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
/*
         1 
        /|\
       / | \
     9/  |7 \3
     / 3 |   \
    0----4----2
     \   | 1 /
     2\  |1 /-2
       \ | /
        \|/
         3 
*/

class Edge {
    int src;
    int dst;
    int weight;

    Edge(int src, int dst, int weight) {
        this.src = src;
        this.dst = dst;
        this.weight = weight;
    }
}

class Graph {

    int nodes;
    // distance is a 2-dimensional array that stores the 
    // shortest distance between [src][dst]
    int distance[][];
    // next is a 2-dimensional array that stores the node next to src. 
    // This is used for the path construction between [src][dst]
    int next[][];
    List<Edge> edge_list = new ArrayList<Edge>();

    Graph (int n) {
        nodes = n;
        distance = new int[n][n];
        next = new int[n][n];

        for (int i=0; i<n; i++) {
            Arrays.fill(distance[i], 999999999); // 999999999 indicates infinite distance
            Arrays.fill(next[i], -1);
        }
    }

    void AddEdge (int src, int dst, int weight, boolean isbidirectional) {

        Edge e = new Edge(src, dst, weight);
        edge_list.add(e);
        if (isbidirectional) {
            e = new Edge(dst, src, weight);
            edge_list.add(e);
        } 
    }

    void Floyd_Warshall() {

        for (int i=0; i<nodes; i++) {
            distance[i][i] = 0;
            next[i][i] = i;
        }

        for (Edge it : edge_list) {
            int weight = it.weight;
            int u = it.src;
            int v = it.dst;
            distance[u][v] = weight;
            next[u][v] = v;
        }

        for (int k=0; k<nodes; k++) {
            for (int i=0; i<nodes; i++) {
                for (int j=0; j<nodes; j++) {
                    if (distance[i][j] > distance[i][k] + distance[k][j]) {
                        distance[i][j] = distance[i][k] + distance[k][j];
                        next[i][j] = next[i][k];
                    }
                }
            }
        }

        System.out.println( "Shortest distance between nodes");
        for (int u=0; u<nodes; u++) {
            for (int v=u+1; v<nodes; v++) {
                System.out.println("\nDistance ( " + u + " - " + v + " ) : " + distance[u][v]);
                PathConstruction(u, v);
            }
        }
    }

    // Construct path from source node to destination node
    void PathConstruction (int src, int dst) {

        System.out.print("# Path between " + src + " and " + dst + " : ");

        if (next[src][dst] == -1) {
            System.out.println( "No path exists");
        } else {
            List<Integer> path = new ArrayList<Integer>();
            path.add(src);

            while (src != dst) {
                src = next[src][dst];
                path.add(src);
            }

            for (int n : path)
                System.out.print(n + " ");
            System.out.println();
        }
    }

    public static void main(String[] args) {

        Graph g = new Graph(5);

        // Edges from node 0
        g.AddEdge(0, 1, 9, true);
        g.AddEdge(0, 3, 2, true);
        g.AddEdge(0, 4, 3, true);

        // Edges from node 1
        g.AddEdge(1, 2, 3, true);
        g.AddEdge(1, 4, 7, true);

        // Edges from node 2
        // Edge from 2 -> 3 is unidirectional. If it was bidirectional, it would introduce negative weight cycle
        // causing the Floyd-Warshall algorithm to fail.
        g.AddEdge(2, 3, -2, false);
        g.AddEdge(2, 4, 1, true);

        // Edges from node 3
        g.AddEdge(3, 4, 1, true);

        g.Floyd_Warshall();
    }    
}

Output

Shortest distance between nodes

Distance ( 0 - 1 ) : 7
# Path between 0 and 1 : 0 4 2 1 

Distance ( 0 - 2 ) : 4
# Path between 0 and 2 : 0 4 2 

Distance ( 0 - 3 ) : 2
# Path between 0 and 3 : 0 3 

Distance ( 0 - 4 ) : 3
# Path between 0 and 4 : 0 4 

Distance ( 1 - 2 ) : 3
# Path between 1 and 2 : 1 2 

Distance ( 1 - 3 ) : 1
# Path between 1 and 3 : 1 2 3 

Distance ( 1 - 4 ) : 2
# Path between 1 and 4 : 1 2 3 4 

Distance ( 2 - 3 ) : -2
# Path between 2 and 3 : 2 3 

Distance ( 2 - 4 ) : -1
# Path between 2 and 4 : 2 3 4 

Distance ( 3 - 4 ) : 1
# Path between 3 and 4 : 3 4

Copyright (c) 2019-2021, Algotree.org.
All rights reserved.