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 : int, dst : int, weight : int) :
        self.src = src
        self.dst = dst
        self.weight = weight

class Graph:

    def __init__(self, arg_nodes : int):

        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 : int, dst : int, weight : int, 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 : int, dst : int):

        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

© 2019-2026 Algotree.org | All rights reserved.

This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org

"The best error message is the one that never shows up. - Thomas Fuchs"