Skip to main content

Floyd Warshall Algorithm

The Floyd-Warshall algorithm is a dynamic programming algorithm used to find the shortest path between all pairs of vertices in a weighted graph. It works by computing a table of distances between each pair of vertices, where the value in the table represents the minimum distance between the two vertices.

The algorithm is efficient for small to medium-sized graphs, and has a time complexity of O(V^3), where V is the number of vertices in the graph. It can handle negative edge weights, but cannot handle negative cycles (a cycle with a negative total weight).

The algorithm works by iterating over all possible pairs of vertices, and considering the possibility of a path between the two vertices that goes through each vertex in the graph. The algorithm updates the table of distances for each pair of vertices until all distances have been computed.

The Floyd-Warshall algorithm is useful in many applications, such as network routing and traffic analysis, as well as in computer science algorithms courses as an example of dynamic programming.

Here given code implementation process.

//C Program
//Floyd Warshall Algorithm
#include <stdio.h>
#include <stdlib.h>
#include <limits.h> //for INT_MAX


struct AjlistNode
{
  int id;//Vertices id
  int weight;
  struct AjlistNode*next;
};

struct Graph
{
  int data; //node key value
  struct AjlistNode*next;
};


int size; //number of nodes

//set node key value
void set_data(struct Graph*node)
{
  if(node!=NULL && size>0)
  {
    int index=0;
    for(index;index<size;index++)
    {
      //set vertic node data
      node[index].data=index;//set node key
      //Initial no AjlistNode
      //set NULL Value
      node[index].next=NULL;
    }
  }
  else
  {
    printf("Vertic Node is Empty");
  }
}
void connect_edge(struct Graph*node, int V ,int E,int weight)
{

  // create Adjacency node
  struct AjlistNode *newEdge=(struct AjlistNode*)malloc(
    sizeof(struct AjlistNode)
    );
  if(newEdge!=NULL)
  {

    newEdge->next=NULL;
    newEdge->id=E;
    newEdge->weight=weight;

    struct AjlistNode *temp=node[V].next;

    if(temp==NULL)
    {
      node[V].next=newEdge;
    }else
    {
        //Add node at last
      while(temp->next!=NULL)
      {
        temp=temp->next;
      }      
      temp->next=newEdge;          
    }
  }else
  {
    printf("\n Memory overflow");

  }
}
  //Add Edge from Two given Nodes
void add_edge(struct Graph*node, int V ,int E,int weight)
{
  //add edge form V to E
  //V and E is Node location
  if(V<size && E <size)
  {

    connect_edge(node,V,E,weight);

  }else
  {
    //not valid Vertices
    printf("Invalid Node Vertices %d  %d", V,E);
  }
}
//Display Adjacency list of vertex
void print_graph(struct Graph*node)

{
  if(node!=NULL)

  {
    struct AjlistNode *temp=NULL;
    for(int index=0;index<size;index++)
    {
      printf("\n Adjacency list of vertex %d  :",index);
      temp=node[index].next;
      while(temp!=NULL)
      {
        //temp->id is graph node vertices
        //in this case temp->id is same as 
        //node[temp->id].data

        printf("  %d",node[temp->id].data);
        temp=temp->next;
      }
    }
  }else
  {
    printf("Empty Graph");
  }
}
//perform floyd warshall algorithm in Adjacency list graph
void floyd_warshall(struct Graph*root)
{

  if(root!=NULL)
  {
    int result[size][size];

    struct AjlistNode *temp=NULL;

    for (int i = 0; i < size; ++i)
    {
      for (int j = 0; j < size; ++j)
      {
        if(i==j)
        {
          result[i][j]=0;
        }
        else
        {
          //Infinity
          result[i][j]=INT_MAX;

          temp=root[i].next;
          //Get the edge information in edge list
          //When edge is exist i to j node
          while(temp!=NULL)
          {
            if(temp->id==j && result[i][j] > temp->weight  )
            {
              result[i][j]=temp->weight;
              
              //when not using more than 2 edge between in two nodes
              //break;
            }
            temp=temp->next;
          }

        }

      }
    }
    printf("\n");
    for (int k = 0; k < size; ++k)
    {
      for (int i = 0; i < size; ++i)
      {

        for (int j = 0; j < size; ++j)
        {
          if(result[i][k] < INT_MAX && 
            result[k][j] < INT_MAX  && 
            (result[i][k] + result[k][j]) < INT_MAX  &&
            result[i][j] > (result[i][k] + result[k][j]) )
          {
            result[i][j] = (result[i][k] + result[k][j]);
          }
          if(result[i][j]<0)
          {
            printf("\nNegative Cycle exist\n");
            return;
          }
        }
        

      }
    }

    for (int i = 0; i < size; ++i)
    {
      for (int j = 0; j < size; ++j)
      {
        if(INT_MAX==result[i][j])
        {
          printf(" INF " );
        }
        else
        {
          printf("  %d  ",result[i][j] );
        }

      }
      printf("\n");
    }
  }
  else
  {
    printf("Empty Graph");
  }
}


int main()

{

  size=5;
  struct Graph*node=NULL;

  node=(struct Graph*)malloc(sizeof(struct Graph)*size);

  if(node==NULL)
  {
    printf("\n Memory overflow");
  }else
  {
        //First set node keys
    set_data(node); 


    //Connected two node with Edges
    add_edge(node,0, 1, 5); 
    add_edge(node,0, 2, 8); 
    add_edge(node,0, 4, 3); 
    add_edge(node,1, 4, 2); 
    add_edge(node,2, 1, 11); 

    // When have 2 paths in same node with different weight
    // In real world scenario
    add_edge(node,3, 0, 4); 
    add_edge(node,3, 0, 5); 
    
    
    add_edge(node,3, 2, 7); 
    add_edge(node,3, 4, 9); 
    add_edge(node,4, 2, 5); 

    print_graph(node);

    floyd_warshall(node);
  }  
  return 0;
}

Output

 Adjacency list of vertex 0  :  1  2  4
 Adjacency list of vertex 1  :  4
 Adjacency list of vertex 2  :  1
 Adjacency list of vertex 3  :  0  0  2  4
 Adjacency list of vertex 4  :  2
  0    5    8   INF   3
 INF   0    7   INF   2
 INF   11    0   INF   13
  4    9    7    0    7
 INF   16    5   INF   0
// C++ Program
// Floyd Warshall Algorithm
#include<iostream>
#include <limits.h> //for INT_MAX
using namespace std;
class AjlistNode {
	public:

	//Vertices node key
	int id;
	int weight;
	AjlistNode *next;
	AjlistNode(int id, int weight) {
		//Set value of node key
		this->id = id;
		this->weight = weight;
		this->next = NULL;
	}
};
class Vertices {
	public:
	int data;
	AjlistNode *next;
    Vertices()
    {
      this->data = 0;
      this->next = NULL;
    }
	
	Vertices(int data) {
		this->data = data;
		this->next = NULL;
	}
};
class MyGraph {
	public:

	//Number of Vertices
	int size;
	Vertices *node;
	MyGraph(int size) {
		//set value
		this->size = size;
		this->node = new Vertices[size];
		this->set_data();
	}
	//Set initial node value
	void set_data() {
		if (this->node == NULL) {
			cout << "\nEmpty Graph";
		} else {
			for (int index = 0; index < this->size; index++) {
				this->node[index] = index;
			}
		}
	}
	//Connect two nodes
	void connect(int start, int last, int weight) {
		AjlistNode *new_edge = new AjlistNode(last, weight);
		if (this->node[start].next == NULL) {
			this->node[start].next = new_edge;
		} else {
			AjlistNode *temp = this->node[start].next;
			while (temp->next != NULL) {
				temp = temp->next;
			}
			temp->next = new_edge;
		}
	}
	//Add edge of two nodes
	void add_edge(int start, int last, int weight) {
		if (start >= 0 &&
			start < this->size &&
			last >= 0 &&
			last < this->size &&
			this->node != NULL) {
			this->connect(start, last, weight);
		} else {
			cout << "\nHere Something Wrong";
		}
	}
	void print_graph() {
		if (this->size > 0 &&
			this->node != NULL) {
			for (int index = 0; index < this->size; index++) {
				cout << "\nAdjacency list of vertex " << index << " :";
				AjlistNode *temp = this->node[index].next;
				while (temp != NULL) {
					cout << " " << this->node[temp->id].data;
					temp = temp->next;
				}
			}
		}
	}
	//perform floyd warshall algorithm in Adjacency list graph
	void floyd_warshall() {
		if (this->node != NULL) {
			int result[size][size];
			AjlistNode *temp = NULL;
			for (int i = 0; i < this->size; ++i) {
				for (int j = 0; j < this->size; ++j) {
					if (i == j) {
						result[i][j] = 0;
					} else {
						//Infinity
						result[i][j] = INT_MAX;
						temp = this->node[i].next;
						//Get the edge information in edge list
						//When edge is exist i to j node
						while (temp != NULL) {
							//when not using more than 2 edge between in two nodes
							//break;

							if (temp->id == j &&
								result[i][j] > temp->weight) {
								result[i][j] = temp->weight;
							}
							temp = temp->next;
						}
					}
				}
			}
			cout << "\n";
			for (int k = 0; k < this->size; ++k) {
				for (int i = 0; i < this->size; ++i) {
					for (int j = 0; j < this->size; ++j) {
						if (result[i][k] < INT_MAX &&
							result[k][j] < INT_MAX &&
							(result[i][k] + result[k][j]) < INT_MAX &&
							result[i][j] > (result[i][k] + result[k][j])) {
							result[i][j] = (result[i][k] + result[k][j]);
						}
						if (result[i][j] < 0) {
							cout << "\nNegative Cycle exist\n";
							return;
						}
					}
				}
			}
			for (int i = 0; i < this->size; ++i) {
				for (int j = 0; j < this->size; ++j) {
					if (INT_MAX == result[i][j]) {
						cout << " INF ";
					} else {
						cout << "  " << result[i][j] << "  ";
					}
				}
				cout << "\n";
			}
		} else {
			cout << "Empty Graph";
		}
	}
};
int main() {
	//5 implies the number of nodes in graph
	MyGraph g =  MyGraph(5);
	//First two parameter indicates number start and last nodes
	//And third parameter indicates weight of edge
	//Connected two node with Edges
	g.add_edge(0, 1, 5);
	g.add_edge(0, 2, 8);
	g.add_edge(0, 4, 3);
	g.add_edge(1, 4, 2);
	g.add_edge(2, 1, 11);
	// When have 2 paths in same node with different weight
	// In real world scenario
	g.add_edge(3, 0, 4);
	g.add_edge(3, 0, 5);
	g.add_edge(3, 2, 7);
	g.add_edge(3, 4, 9);
	g.add_edge(4, 2, 5);
	g.print_graph();
	g.floyd_warshall();
	return 0;
}

Output

Adjacency list of vertex 0 : 1 2 4
Adjacency list of vertex 1 : 4
Adjacency list of vertex 2 : 1
Adjacency list of vertex 3 : 0 0 2 4
Adjacency list of vertex 4 : 2
  0    5    8   INF   3
 INF   0    7   INF   2
 INF   11    0   INF   13
  4    9    7    0    7
 INF   16    5   INF   0
// Java Program
// Floyd Warshall Algorithm
class AjlistNode {
  //Vertices node key
  public int id; 
  public int weight; 
  public AjlistNode next;

  public AjlistNode(int id,int weight) {
    //Set value of node key
    this.id = id;
    this.weight=weight;
    this.next = null;
  }
}
class Vertices {

  public int data;
  public AjlistNode next;

  public Vertices(int data) {
    this.data = data;
    this.next = null;
  }
}

public class MyGraph
{

  //Number of Vertices
  public int size;
    
  public Vertices []node;

  public MyGraph(int size)
  {
    //set value
    this.size = size;
    this.node = new Vertices[size];
    this.set_data();
    
  }

  //Set initial node value
  public void set_data()
  {
    if(node == null)
    {
      System.out.println("\nEmpty Graph");
    }else
    {
      for(int index=0;index<size;index++)
      {

        node[index]=new Vertices(index); 
      }
    }
  }

  //Connect two nodes
  public void connect(int start,int last ,int weight)
  {
    AjlistNode new_edge=new AjlistNode(last,weight);

    if(node[start].next==null)
    {
      node[start].next=new_edge;
    }else
    {
      AjlistNode temp=node[start].next;

      while(temp.next!=null)
      {
        temp=temp.next;
      }
      temp.next=new_edge;
    }
  }
  //Add edge of two nodes
  public void add_edge(int start,int last,int weight)
  {
    if(start>=0 && start < size && last >= 0 &&  last < size && node != null)
    {
      connect(start,last,weight);
    }
    else
    {
      System.out.println("\nHere Something Wrong");
    }
  }

  public void print_graph()
  {

    if(size >0 && node!=null)
    {
      for(int index = 0; index < size; index++)
      {
        System.out.print("\nAdjacency list of vertex "+index+" :");
        AjlistNode temp = node[index].next;
        while(temp != null)
        {
          System.out.print("  "+node[temp.id].data);
          temp=temp.next;
        }
      }
    }
  }
  //perform floyd warshall algorithm in Adjacency list graph
  public void floyd_warshall() 
  {
    if (node != null) 
    {
      int[][] result = new int[size][size];

      AjlistNode temp = null;

      for (int i = 0; i < size; ++i) 
      {
        for (int j = 0; j < size; ++j) 
        {
          if (i == j) {
            result[i][j] = 0;
          } else 
          {
            //Infinity
            result[i][j] = Integer.MAX_VALUE;
            temp = node[i].next;
            //Get the edge information in edge list
            //When edge is exist i to j node

            while (temp != null) 
            {
              

              if (temp.id == j && result[i][j] > temp.weight) 
              {
                
                result[i][j] = temp.weight;
                //when not using more than 2 edge between in two nodes
                //break;
              }
              temp = temp.next;
            }
          }
        }
      }
      System.out.print("\n");
      for (int k = 0; k < size; ++k) 
      {
        for (int i = 0; i < size; ++i) 
        {
          for (int j = 0; j < size; ++j) 
          {
            if (result[i][k] < Integer.MAX_VALUE && result[k][j] < Integer.MAX_VALUE && (result[i][k] + result[k][j]) < Integer.MAX_VALUE && result[i][j] > (result[i][k] + result[k][j])) 
            {
              result[i][j] = (result[i][k] + result[k][j]);
            }
            if(result[i][j]<0)
            {
              System.out.print("\nNegative Cycle exist\n");
              return;
            }
          }


        }
      }
      for (int i = 0; i < size; ++i) 
      {
        for (int j = 0; j < size; ++j) 
        {
          if (Integer.MAX_VALUE == result[i][j]) 
          {
            System.out.print("  INF  ");
          } 
          else 
          {
            System.out.print("  "+result[i][j]+"  " );
          }
        }
        System.out.print("\n");
      }
    } else {
      System.out.print("Empty Graph");
    }
  }
  public static void main(String[] args) 
  {

    //5 implies the number of nodes in graph
    MyGraph g=new MyGraph(5);

    //First two parameter indicates number start and last nodes
    //And third parameter indicates weight of edge
    //Connected two node with Edges
    g.add_edge(0, 1, 5); 
    g.add_edge(0, 2, 8); 
    g.add_edge(0, 4, 3); 
    g.add_edge(1, 4, 2); 
    g.add_edge(2, 1, 11); 

    // When have 2 paths in same node with different weight
    // In real world scenario
    g.add_edge(3, 0, 4); 
    g.add_edge(3, 0, 5); 
    
    
    g.add_edge(3, 2, 7); 
    g.add_edge(3, 4, 9); 
    g.add_edge(4, 2, 5); 

    
    g.print_graph();
    g.floyd_warshall();
  }
}

Output

Adjacency list of vertex 0 : 1 2 4
Adjacency list of vertex 1 : 4
Adjacency list of vertex 2 : 1
Adjacency list of vertex 3 : 0 0 2 4
Adjacency list of vertex 4 : 2
  0    5    8   INF   3
 INF   0    7   INF   2
 INF   11    0   INF   13
  4    9    7    0    7
 INF   16    5   INF   0
// C# Program
// Floyd Warshall Algorithm
using System;
public class AjlistNode {
	//Vertices node key
	public int id;
	public int weight;
	public AjlistNode next;
	public AjlistNode(int id, int weight) {
		//Set value of node key
		this.id = id;
		this.weight = weight;
		this.next = null;
	}
}
public class Vertices {
	public int data;
	public AjlistNode next;
	public Vertices(int data) {
		this.data = data;
		this.next = null;
	}
}
public class MyGraph {
	//Number of Vertices
	public int size;
	public Vertices[] node;
	public MyGraph(int size) {
		//set value
		this.size = size;
		this.node = new Vertices[size];
		this.set_data();
	}
	//Set initial node value
	public void set_data() {
		if (node == null) {
			Console.WriteLine("\nEmpty Graph");
		} else {
			for (int index = 0; index < size; index++) {
				node[index] = new Vertices(index);
			}
		}
	}
	//Connect two nodes
	public void connect(int start, int last, int weight) {
		AjlistNode new_edge = new AjlistNode(last, weight);
		if (node[start].next == null) {
			node[start].next = new_edge;
		} else {
			AjlistNode temp = node[start].next;
			while (temp.next != null) {
				temp = temp.next;
			}
			temp.next = new_edge;
		}
	}
	//Add edge of two nodes
	public void add_edge(int start, int last, int weight) {
		if (start >= 0 &&
			start < size &&
			last >= 0 &&
			last < size &&
			node != null) {
			connect(start, last, weight);
		} else {
			Console.WriteLine("\nHere Something Wrong");
		}
	}
	public void print_graph() {
		if (size > 0 &&
			node != null) {
			for (int index = 0; index < size; index++) {
				Console.Write("\nAdjacency list of vertex " + index + " :");
				AjlistNode temp = node[index].next;
				while (temp != null) {
					Console.Write("  " + node[temp.id].data);
					temp = temp.next;
				}
			}
		}
	}
	//perform floyd warshall algorithm in Adjacency list graph
	public void floyd_warshall() {
		if (node != null) {
			int[,] result = new int[size,size];
			AjlistNode temp = null;
			for (int i = 0; i < size; ++i) {
				for (int j = 0; j < size; ++j) {
					if (i == j) {
						result[i,j] = 0;
					} else {
						//Infinity
						result[i,j] = int.MaxValue;
						temp = node[i].next;
						//Get the edge information in edge list
						//When edge is exist i to j node
						while (temp != null) {
							//when not using more than 2 edge between in two nodes
							//break;

							if (temp.id == j &&
								result[i,j] > temp.weight) {
								result[i,j] = temp.weight;
							}
							temp = temp.next;
						}
					}
				}
			}
			Console.Write("\n");
			for (int k = 0; k < size; ++k) {
				for (int i = 0; i < size; ++i) {
					for (int j = 0; j < size; ++j) {
						if (result[i,k] < int.MaxValue &&
							result[k,j] < int.MaxValue &&
							(result[i,k] + result[k,j]) < int.MaxValue &&
							result[i,j] > (result[i,k] + result[k,j])) {
							result[i,j] = (result[i,k] + result[k,j]);
						}
						if (result[i,j] < 0) {
							Console.Write("\nNegative Cycle exist\n");
							return;
						}
					}
				}
			}
			for (int i = 0; i < size; ++i) {
				for (int j = 0; j < size; ++j) {
					if (int.MaxValue == result[i,j]) {
						Console.Write(" INF ");
					} else {
						Console.Write("  " + result[i,j] + "  ");
					}
				}
				Console.Write("\n");
			}
		} else {
			Console.Write("Empty Graph");
		}
	}
	public static void Main(String[] args) {
		//5 implies the number of nodes in graph
		MyGraph g = new MyGraph(5);
		g.add_edge(0, 1, 5);
		g.add_edge(0, 2, 8);
		g.add_edge(0, 4, 3);
		g.add_edge(1, 4, 2);
		g.add_edge(2, 1, 11);
		g.add_edge(3, 0, 4);
		g.add_edge(3, 0, 5);
		g.add_edge(3, 2, 7);
		g.add_edge(3, 4, 9);
		g.add_edge(4, 2, 5);
		g.print_graph();
		g.floyd_warshall();
	}
}

Output

Adjacency list of vertex 0 :  1  2  4
Adjacency list of vertex 1 :  4
Adjacency list of vertex 2 :  1
Adjacency list of vertex 3 :  0  0  2  4
Adjacency list of vertex 4 :  2
  0    5    8   INF   3
 INF   0    7   INF   2
 INF   11    0   INF   13
  4    9    7    0    7
 INF   16    5   INF   0
<?php
// Php Program
// Floyd Warshall Algorithm
class AjlistNode {
	//Vertices node key

	public $id;
	public $weight;
	public $next;

	function __construct($id, $weight) {
		//Set value of node key
		$this->id = $id;
		$this->weight = $weight;
		$this->next = null;
	}
}
class Vertices {
	public $data;
	public $next;

	function __construct($data) {
		$this->data = $data;
		$this->next = null;
	}
}
class MyGraph {
	//Number of Vertices

	public $size;
	public $node;

	function __construct($size) {
		//set value
		$this->size = $size;
		$this->node = array_fill(0, $size, null);
		$this->set_data();
	}
	//Set initial node value

	public 	function set_data() {
		if ($this->node == null) {
			echo("\nEmpty Graph");
		} else {
			for ($index = 0; $index < $this->size; $index++) {
				$this->node[$index] = new Vertices($index);
			}
		}
	}
	//Connect two nodes

	public 	function connect($start, $last, $weight) {
		$new_edge = new AjlistNode($last, $weight);
		if ($this->node[$start]->next == null) {
			$this->node[$start]->next = $new_edge;
		} else {
			$temp = $this->node[$start]->next;
			while ($temp->next != null) {
				$temp = $temp->next;
			}
			$temp->next = $new_edge;
		}
	}
	//Add edge of two nodes

	public 	function add_edge($start, $last, $weight) {
		if ($start >= 0 &&
			$start < $this->size &&
			$last >= 0 &&
			$last < $this->size &&
			$this->node != null) {
			$this->connect($start, $last, $weight);
		} else {
			echo("\nHere Something Wrong");
		}
	}
	public 	function print_graph() {
		if ($this->size > 0 &&
			$this->node != null) {
			for ($index = 0; $index < $this->size; $index++) {
				echo("\nAdjacency list of vertex ". $index ." :");
				$temp = $this->node[$index]->next;
				while ($temp != null) {
					echo(" ". $this->node[$temp->id]->data);
					$temp = $temp->next;
				}
			}
		}
	}
	//perform floyd warshall algorithm in Adjacency list graph

	public 	function floyd_warshall() {
		if ($this->node != null) {
			$result = array_fill(0, $this->size, array_fill(0, $this->size, 0));
			$temp = null;
			for ($i = 0; $i < $this->size; ++$i) {
				for ($j = 0; $j < $this->size; ++$j) {
					if ($i == $j) {
						$result[$i][$j] = 0;
					} else {
						//Infinity
						$result[$i][$j] = PHP_INT_MAX;
						$temp = $this->node[$i]->next;
						//Get the edge information in edge list
						//When edge is exist i to j node
						while ($temp != null) {
							

							if ($temp->id == $j &&
								$result[$i][$j] > $temp->weight) {
								$result[$i][$j] = $temp->weight;
                              	//when not using more than 2 edge between in two nodes
								//break;
							}
							$temp = $temp->next;
						}
					}
				}
			}
			echo("\n");
			for ($k = 0; $k < $this->size; ++$k) {
				for ($i = 0; $i < $this->size; ++$i) {
					for ($j = 0; $j < $this->size; ++$j) {
						if ($result[$i][$k] < PHP_INT_MAX &&
							$result[$k][$j] < PHP_INT_MAX &&
							($result[$i][$k] + $result[$k][$j]) < PHP_INT_MAX &&
							$result[$i][$j] > ($result[$i][$k] + $result[$k][$j])) {
							$result[$i][$j] = ($result[$i][$k] + $result[$k][$j]);
						}
						if ($result[$i][$j] < 0) {
							echo("\nNegative Cycle exist\n");
							return;
						}
					}
				}
			}
			for ($i = 0; $i < $this->size; ++$i) {
				for ($j = 0; $j < $this->size; ++$j) {
					if (PHP_INT_MAX == $result[$i][$j]) {
						echo(" INF ");
					} else {
						echo("  ". $result[$i][$j] ."  ");
					}
				}
				echo("\n");
			}
		} else {
			echo("Empty Graph");
		}
	}
}

function main() {
	//5 implies the number of nodes in graph
	$g = new MyGraph(5);
	//First two parameter indicates number start and last nodes
	//And third parameter indicates weight of edge
	//Connected two node with Edges
	$g->add_edge(0, 1, 5);
	$g->add_edge(0, 2, 8);
	$g->add_edge(0, 4, 3);
	$g->add_edge(1, 4, 2);
	$g->add_edge(2, 1, 11);
	// When have 2 paths in same node with different weight
	// In real world scenario
	$g->add_edge(3, 0, 4);
	$g->add_edge(3, 0, 5);
	$g->add_edge(3, 2, 7);
	$g->add_edge(3, 4, 9);
	$g->add_edge(4, 2, 5);
	$g->print_graph();
	$g->floyd_warshall();

}
main();

Output

Adjacency list of vertex 0 : 1 2 4
Adjacency list of vertex 1 : 4
Adjacency list of vertex 2 : 1
Adjacency list of vertex 3 : 0 0 2 4
Adjacency list of vertex 4 : 2
  0    5    8   INF   3
 INF   0    7   INF   2
 INF   11    0   INF   13
  4    9    7    0    7
 INF   16    5   INF   0
// Node Js Program
// Floyd Warshall Algorithm
class AjlistNode {
	//Vertices node key

	constructor(id, weight) {
		//Set value of node key
		this.id = id;
		this.weight = weight;
		this.next = null;
	}
}
class Vertices {
	constructor(data) {
		this.data = data;
		this.next = null;
	}
}
class MyGraph {
	//Number of Vertices

	constructor(size) {
		//set value
		this.size = size;
		this.node = Array(size).fill(null);
		this.set_data();
	}

	//Set initial node value
	set_data() {
		if (this.node == null) {
			process.stdout.write("\nEmpty Graph");
		} else {
			for (var index = 0; index < this.size; index++) {
				this.node[index] = new Vertices(index);
			}
		}
	}

	//Connect two nodes
	connect(start, last, weight) {
		var new_edge = new AjlistNode(last, weight);
		if (this.node[start].next == null) {
			this.node[start].next = new_edge;
		} else {
			var temp = this.node[start].next;
			while (temp.next != null) {
				temp = temp.next;
			}
			temp.next = new_edge;
		}
	}

	//Add edge of two nodes
	add_edge(start, last, weight) {
		if (start >= 0 &&
			start < this.size &&
			last >= 0 &&
			last < this.size &&
			this.node != null) {
			this.connect(start, last, weight);
		} else {
			process.stdout.write("\nHere Something Wrong");
		}
	}
	print_graph() {
		if (this.size > 0 &&
			this.node != null) {
			for (var index = 0; index < this.size; index++) {
				process.stdout.write("\nAdjacency list of vertex " + index + " :");
				var temp = this.node[index].next;
				while (temp != null) {
					process.stdout.write(" " + this.node[temp.id].data);
					temp = temp.next;
				}
			}
		}
	}

	//perform floyd warshall algorithm in Adjacency list graph
	floyd_warshall() {
		if (this.node != null) {
			var result = Array(this.size).fill(0).map(() => new Array(this.size).fill(0));
			var temp = null;
			for (var i = 0; i < this.size; ++i) {
				for (var j = 0; j < this.size; ++j) {
					if (i == j) {
						result[i][j] = 0;
					} else {
						//Infinity
						result[i][j] = Number.MAX_VALUE;
						temp = this.node[i].next;
						//Get the edge information in edge list
						//When edge is exist i to j node
						while (temp != null) {
							//when not using more than 2 edge between in two nodes
							//break;

							if (temp.id == j &&
								result[i][j] > temp.weight) {
								result[i][j] = temp.weight;
							}
							temp = temp.next;
						}
					}
				}
			}

			process.stdout.write("\n");
			for (var k = 0; k < this.size; ++k) {
				for (var i = 0; i < this.size; ++i) {
					for (var j = 0; j < this.size; ++j) {
						if (result[i][k] < Number.MAX_VALUE &&
							result[k][j] < Number.MAX_VALUE &&
							(result[i][k] + result[k][j]) < Number.MAX_VALUE &&
							result[i][j] > (result[i][k] + result[k][j])) {
							result[i][j] = (result[i][k] + result[k][j]);
						}

						if (result[i][j] < 0) {
							process.stdout.write("\nNegative Cycle exist\n");
							return;
						}
					}
				}
			}

			for (var i = 0; i < this.size; ++i) {
				for (var j = 0; j < this.size; ++j) {
					if (Number.MAX_VALUE == result[i][j]) {
						process.stdout.write(" INF ");
					} else {
						process.stdout.write("  " + result[i][j] + "  ");
					}
				}

				process.stdout.write("\n");
			}
		} else {
			process.stdout.write("Empty Graph");
		}
	}
}

function main(args) {
	//5 implies the number of nodes in graph
	var g = new MyGraph(5);
	//First two parameter indicates number start and last nodes
	//And third parameter indicates weight of edge
	//Connected two node with Edges
	g.add_edge(0, 1, 5);
	g.add_edge(0, 2, 8);
	g.add_edge(0, 4, 3);
	g.add_edge(1, 4, 2);
	g.add_edge(2, 1, 11);
	// When have 2 paths in same node with different weight
	// In real world scenario
	g.add_edge(3, 0, 4);
	g.add_edge(3, 0, 5);
	g.add_edge(3, 2, 7);
	g.add_edge(3, 4, 9);
	g.add_edge(4, 2, 5);
	g.print_graph();
	g.floyd_warshall();
}

main();

Output

Adjacency list of vertex 0 : 1 2 4
Adjacency list of vertex 1 : 4
Adjacency list of vertex 2 : 1
Adjacency list of vertex 3 : 0 0 2 4
Adjacency list of vertex 4 : 2
  0    5    8   INF   3
 INF   0    7   INF   2
 INF   11    0   INF   13
  4    9    7    0    7
 INF   16    5   INF   0
#  Python 3 Program
#  Floyd Warshall Algorithm
import sys
class AjlistNode :
	# Vertices node key
	def __init__(self, id, weight) :
		# Set value of node key
		self.id = id
		self.weight = weight
		self.next = None
	

class Vertices :
	def __init__(self, data) :
		self.data = data
		self.next = None
	

class MyGraph :
	# Number of Vertices
	def __init__(self, size) :
		# set value
		self.size = size
		self.node = [None] * size
		self.set_data()
	
	# Set initial node value
	def set_data(self) :
		if (self.node == None) :
			print("\nEmpty Graph", end = "")
		else :
			index = 0
			while (index < self.size) :
				self.node[index] = Vertices(index)
				index += 1
			
		
	
	# Connect two nodes
	def connect(self, start, last, weight) :
		new_edge = AjlistNode(last, weight)
		if (self.node[start].next == None) :
			self.node[start].next = new_edge
		else :
			temp = self.node[start].next
			while (temp.next != None) :
				temp = temp.next
			
			temp.next = new_edge
		
	
	# Add edge of two nodes
	def add_edge(self, start, last, weight) :
		if (start >= 0 and start < self.size and 
            last >= 0 and last < self.size and self.node != None) :
			self.connect(start, last, weight)
		else :
			print("\nHere Something Wrong", end = "")
		
	
	def print_graph(self) :
		if (self.size > 0 and self.node != None) :
			index = 0
			while (index < self.size) :
				print("\nAdjacency list of vertex ", index ," :", end = "")
				temp = self.node[index].next
				while (temp != None) :
					print(" ", self.node[temp.id].data, end = "")
					temp = temp.next
				
				index += 1
			
		
	
	# perform floyd warshall algorithm in Adjacency list graph
	def floyd_warshall(self) :
		if (self.node != None) :
			result = [[0] * self.size
                      for _ in range(self.size)]
			temp = None
			i = 0
			while (i < self.size) :
				j = 0
				while (j < self.size) :
					if (i == j) :
						result[i][j] = 0
					else :
						# Infinity
						result[i][j] = sys.maxsize
						temp = self.node[i].next
						# Get the edge information in edge list
						# When edge is exist i to j node
						while (temp != None) :
							# when not using more than 2 edge between in two nodes
							# break

							if (temp.id == j and result[i][j] > temp.weight) :
								result[i][j] = temp.weight
							
							temp = temp.next
						
					
					j += 1
				
				i += 1
			
			print("\n", end = "")
			k = 0
			while (k < self.size) :
				i = 0
				while (i < self.size) :
					j = 0
					while (j < self.size) :
						if (result[i][k] < sys.maxsize and
                            result[k][j] < sys.maxsize 
							and(result[i][k] + result[k][j]) < sys.maxsize and 
                        result[i][j] > (result[i][k] + result[k][j])) :
							result[i][j] = (result[i][k] + result[k][j])
						
						if (result[i][j] < 0) :
							print("\nNegative Cycle exist\n", end = "")
							return
						
						j += 1
					
					i += 1
				
				k += 1
			
			i = 0
			while (i < self.size) :
				j = 0
				while (j < self.size) :
					if (sys.maxsize == result[i][j]) :
						print(" INF ", end = "")
					else :
						print(" ", result[i][j] ," ", end = "")
					
					j += 1
				
				print("\n", end = "")
				i += 1
			
		else :
			print("Empty Graph", end = "")
		
	

def main() :
	# 5 implies the number of nodes in graph
	g = MyGraph(5)
	# First two parameter indicates number start and last nodes
	# And third parameter indicates weight of edge
	# Connected two node with Edges
	g.add_edge(0, 1, 5)
	g.add_edge(0, 2, 8)
	g.add_edge(0, 4, 3)
	g.add_edge(1, 4, 2)
	g.add_edge(2, 1, 11)
	#  When have 2 paths in same node with different weight
	#  In real world scenario
	g.add_edge(3, 0, 4)
	g.add_edge(3, 0, 5)
	g.add_edge(3, 2, 7)
	g.add_edge(3, 4, 9)
	g.add_edge(4, 2, 5)
	g.print_graph()
	g.floyd_warshall()


if __name__ == "__main__":
	main()

Output

Adjacency list of vertex  0  :  1  2  4
Adjacency list of vertex  1  :  4
Adjacency list of vertex  2  :  1
Adjacency list of vertex  3  :  0  0  2  4
Adjacency list of vertex  4  :  2
  0    5    8   INF   3
 INF   0    7   INF   2
 INF   11    0   INF   13
  4    9    7    0    7
 INF   16    5   INF   0
#  Ruby Program
#  Floyd Warshall Algorithm
class AjlistNode
    # Define the accessor and reader of class AjlistNode
    attr_reader :id, :weight, :next
    attr_accessor :id, :weight, :next 
	# Vertices node key
	def initialize(id, weight) 
		# Set value of node key
		self.id = id
		self.weight = weight
		self.next = nil
	end
end
class Vertices
    # Define the accessor and reader of class Vertices
    attr_reader :data, :next
    attr_accessor :data, :next 
	
	def initialize(data) 
		self.data = data
		self.next = nil
	end
end
class MyGraph
    # Define the accessor and reader of class MyGraph
    attr_reader :size, :node
    attr_accessor :size, :node 
	# Number of Vertices
	def initialize(size) 
		# set value
		self.size = size
		self.node = Array.new(size) {nil}
		self.set_data()
	end
	# Set initial node value
	def set_data() 
		if (@node == nil) 
			print("\nEmpty Graph")
		else 
			index = 0
			while (index < @size) 
				@node[index] = Vertices.new(index)
				index += 1
			end
		end
	end
	# Connect two nodes
	def connect(start, last, weight) 
		new_edge = AjlistNode.new(last, weight)
		if (@node[start].next == nil) 
			@node[start].next = new_edge
		else 
			temp = @node[start].next
			while (temp.next != nil) 
				temp = temp.next
			end
			temp.next = new_edge
		end
	end
	# Add edge of two nodes
	def add_edge(start, last, weight) 
		if (start >= 0 &&
			start < @size &&
			last >= 0 &&
			last < @size &&
			@node != nil) 
			self.connect(start, last, weight)
		else 
			print("\nHere Something Wrong")
		end
	end
	def print_graph() 
		if (@size > 0 &&
			@node != nil) 
			index = 0
			while (index < @size) 
				print("\nAdjacency list of vertex ", index ,"  :")
				temp = @node[index].next
				while (temp != nil) 
					print(" ", @node[temp.id].data)
					temp = temp.next
				end
				index += 1
			end
		end
	end
	# perform floyd warshall algorithm in Adjacency list graph
	def floyd_warshall() 
		if (@node != nil) 
			result = Array.new(@size) { Array.new(@size){0}}
			temp = nil
			i = 0
			while (i < @size) 
				j = 0
				while (j < @size) 
					if (i == j) 
						result[i][j] = 0
					else 
						# Infinity
						result[i][j] = (2 ** (0. size * 8 - 2))
						temp = @node[i].next
						# Get the edge information in edge list
						# When edge is exist i to j node
						while (temp != nil) 
							# when not using more than 2 edge between in two nodes
							# break

							if (temp.id == j &&
								result[i][j] > temp.weight) 
								result[i][j] = temp.weight
							end
							temp = temp.next
						end
					end
					j += 1
				end
				i += 1
			end
			print("\n")
			k = 0
			while (k < @size) 
				i = 0
				while (i < @size) 
					j = 0
					while (j < @size) 
						if (result[i][k] < (2 ** (0. size * 8 - 2)) &&
							result[k][j] < (2 ** (0. size * 8 - 2)) &&
							(result[i][k] + result[k][j]) < (2 ** (0. size * 8 - 2)) &&
							result[i][j] > (result[i][k] + result[k][j])) 
							result[i][j] = (result[i][k] + result[k][j])
						end
						if (result[i][j] < 0) 
							print("\nNegative Cycle exist\n")
							return
						end
						j += 1
					end
					i += 1
				end
				k += 1
			end
			i = 0
			while (i < @size) 
				j = 0
				while (j < @size) 
					if ((2 ** (0. size * 8 - 2)) == result[i][j]) 
						print(" INF ")
					else 
						print("  ", result[i][j] ,"  ")
					end
					j += 1
				end
				print("\n")
				i += 1
			end
		else 
			print("Empty Graph")
		end
	end
end
def main() 
	# 5 implies the number of nodes in graph
	g = MyGraph.new(5)
	# First two parameter indicates number start and last nodes
	# And third parameter indicates weight of edge
	# Connected two node with Edges
	g.add_edge(0, 1, 5)
	g.add_edge(0, 2, 8)
	g.add_edge(0, 4, 3)
	g.add_edge(1, 4, 2)
	g.add_edge(2, 1, 11)
	#  When have 2 paths in same node with different weight
	#  In real world scenario
	g.add_edge(3, 0, 4)
	g.add_edge(3, 0, 5)
	g.add_edge(3, 2, 7)
	g.add_edge(3, 4, 9)
	g.add_edge(4, 2, 5)
	g.print_graph()
	g.floyd_warshall()
end
main()

Output

Adjacency list of vertex 0  : 1 2 4
Adjacency list of vertex 1  : 4
Adjacency list of vertex 2  : 1
Adjacency list of vertex 3  : 0 0 2 4
Adjacency list of vertex 4  : 2
  0    5    8   INF   3  
 INF   0    7   INF   2  
 INF   11    0   INF   13  
  4    9    7    0    7  
 INF   16    5   INF   0  

// Scala Program
// Floyd Warshall Algorithm
class AjlistNode(var id: Int,
	var next: AjlistNode,
		var weight: Int) {

	def this(id: Int, weight: Int) {
		//Set value
      	this(id,null,weight);
	}
}
class Vertices(var data: Int,
	var next: AjlistNode) {

	def this(data: Int) {
		this(data,null);
	}
}
class MyGraph(var size: Int,
	var node: Array[Vertices]) {
	//Number of Vertices
	def this(size: Int) {
		this(size,Array.fill[Vertices](size)(null));
		this.set_data();
	}
	//Set initial node value
	def set_data(): Unit = {
		if (node == null) {
			print("\nEmpty Graph");
		} else {
			var index: Int = 0;
			while (index < size) {
				node(index) = new Vertices(index);
				index += 1;
			}
		}
	}
	//Connect two nodes
	def connect(start: Int, last: Int, weight: Int): Unit = {
		var new_edge: AjlistNode = new AjlistNode(last, weight);

		if (node(start).next == null) {
			node(start).next = new_edge;
		} else {
			var temp: AjlistNode = node(start).next;
			while (temp.next != null) {
				temp = temp.next;
			}
			temp.next = new_edge;
		}
	}
	//Add edge of two nodes
	def add_edge(start: Int, last: Int, weight: Int): Unit = {
		if (start >= 0 &&
			start < size &&
			last >= 0 &&
			last < size &&
			node != null) {
			connect(start, last, weight);
		} else {
			print("\nHere Something Wrong");
		}
	}
	def print_graph(): Unit = {
		if (size > 0 &&
			node != null) {
			var index: Int = 0;
			while (index < size) {
				print("\nAdjacency list of vertex " + index + " :");
				var temp: AjlistNode = node(index).next;
				while (temp != null) {
					print(" " + node(temp.id).data);
					temp = temp.next;
				}
				index += 1;
			}
		}
	}
	//perform floyd warshall algorithm in Adjacency list graph
	def floyd_warshall(): Unit = {
		if (node != null) {
			var result:Array[Array[Int]] = Array.fill[Int](this.size,this.size)(0);
			var temp: AjlistNode = null;
			var i: Int = 0;
          	var j: Int = 0;
			while (i < size) {
				j = 0;
				while (j < size) {
					if (i == j) {
						result(i)(j) = 0;
					} else {
						//Infinity
						result(i)(j) = Int.MaxValue;
						temp = node(i).next;

						//Get the edge information in edge list
						//When edge is exist i to j node
						while (temp != null) {
							//when not using more than 2 edge between in two nodes
							//break;

							if (temp.id == j &&
								result(i)(j) > temp.weight) {
								result(i)(j) = temp.weight;
							}
							temp = temp.next;
						}
					}
					j += 1;
				}
				i += 1;
			}
			print("\n");
			var k: Int = 0;
			while (k < size) {
				i = 0;
				while (i < size) {
					j = 0;
					while (j < size) {
						if (result(i)(k) < Int.MaxValue &&
							result(k)(j) < Int.MaxValue &&
							(result(i)(k) + result(k)(j)) < Int.MaxValue &&
							result(i)(j) > (result(i)(k) + result(k)(j))) {
							result(i)(j) = (result(i)(k) + result(k)(j));
						}
						if (result(i)(j) < 0) {
							print("\nNegative Cycle exist\n");

							return;
						}
						j += 1;
					}
					i += 1;
				}
				k += 1;
			}
			i = 0;
			while (i < size) {
				j = 0;
				while (j < size) {
					if (Int.MaxValue == result(i)(j)) {
						print(" INF ");
					} else {
						print("  " + result(i)(j) + "  ");
					}
					j += 1;
				}
				print("\n");
				i += 1;
			}
		} else {
			print("Empty Graph");
		}
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		//5 implies the number of nodes in graph
		var g: MyGraph = new MyGraph(5);

		//First two parameter indicates number start and last nodes
		//And third parameter indicates weight of edge
		//Connected two node with Edges
		g.add_edge(0, 1, 5);
		g.add_edge(0, 2, 8);
		g.add_edge(0, 4, 3);
		g.add_edge(1, 4, 2);
		g.add_edge(2, 1, 11);

		// When have 2 paths in same node with different weight
		// In real world scenario
		g.add_edge(3, 0, 4);
		g.add_edge(3, 0, 5);
		g.add_edge(3, 2, 7);
		g.add_edge(3, 4, 9);
		g.add_edge(4, 2, 5);
		g.print_graph();
		g.floyd_warshall();
	}
}

Output

Adjacency list of vertex 0 : 1 2 4
Adjacency list of vertex 1 : 4
Adjacency list of vertex 2 : 1
Adjacency list of vertex 3 : 0 0 2 4
Adjacency list of vertex 4 : 2
  0    5    8   INF   3
 INF   0    7   INF   2
 INF   11    0   INF   13
  4    9    7    0    7
 INF   16    5   INF   0
// Swift Program
// Floyd Warshall Algorithm
class AjlistNode {
  //Vertices node key
  var id: Int;
  var weight: Int;
  var next: AjlistNode? ;
  init(_ id: Int, _ weight: Int) {
    //Set value of node key
    self.id = id;
    self.weight = weight;
    self.next = nil;
  }
}
class Vertices {
  var data: Int;
  var next: AjlistNode? ;
  init(_ value: Int) {
    self.data = value;
    self.next = nil;
  }
}
class MyGraph {
  //Number of Vertices
  var size: Int;
  var node: [Vertices]? = [Vertices]() ;

  init(_ size: Int) {
    //set value
    self.size = size;
    var i = 0;
    while (i<size) {
      self.node!.append(Vertices(i));
      i+=1;

    }
  }
  //Connect two nodes
  func connect(_ start: Int, _ last: Int, _ weight: Int) {
    let new_edge: AjlistNode? = AjlistNode(last, weight);
    if (self.node![start].next == nil) {
      self.node![start].next = new_edge;
    } else {
      var temp: AjlistNode? = self.node![start].next;
      while (temp!.next != nil) {
        temp = temp!.next;
      }
      temp!.next = new_edge;
    }
  }
  //Add edge of two nodes
  func add_edge(_ start: Int, _ last: Int, _ weight: Int) {
    if (start >= 0 &&
      start < self.size &&
      last >= 0 &&
      last < self.size &&
      self.node != nil) {
      self.connect(start, last, weight);
  
    } else {
      print("\nHere Something Wrong", terminator: "");
    }
  }
  func print_graph() {
    if (self.size > 0 &&
      self.node != nil) {
      var index: Int = 0;
      while (index < self.size) {
        print("\nAdjacency list of vertex ", index ," :", terminator: "");
        var temp: AjlistNode? = self.node![index].next;
        while (temp != nil) {
          print(" ", self.node![temp!.id].data, terminator: "");
          temp = temp!.next;
        }
        index += 1;
      }
    }
  }
  //perform floyd warshall algorithm in Adjacency list graph
  func floyd_warshall() {
    if (self.node != nil) {
      var result: [[Int]] = Array( repeating : Array(repeating: 0, count: self.size),count: self.size);
      var temp: AjlistNode? = nil;
      var i: Int = 0;
      var j: Int = 0;
      var k: Int = 0;
      while (i < self.size) {
        j = 0;

        while (j < self.size) {
          if (i == j) {
            result[i][j] = 0;
          } else {
            //Infinity
            result[i][j] = Int.max;
            temp = self.node![i].next;
            //Get the edge information in edge list
            //When edge is exist i to j node
            while (temp != nil) {
              

              if (temp!.id == j &&
                result[i][j] > temp!.weight) {
                result[i][j] = temp!.weight;
                //when not using more than 2 edge between in two nodes
                //break;
              }
              temp = temp!.next;
            }
          }
          j += 1;
        }
        i += 1;
      }
      print("\n", terminator: "");
    
      while (k < self.size) {
        i = 0;
        while (i < self.size) {
          j = 0;
          while (j < self.size) {
            if (result[i][k] < Int.max &&
              result[k][j] < Int.max &&
              (result[i][k] + result[k][j]) < Int.max &&
              result[i][j] > (result[i][k] + result[k][j])) {
              result[i][j] = (result[i][k] + result[k][j]);
            }
            if (result[i][j] < 0) {
              print("\nNegative Cycle exist\n", terminator: "");
              return;
            }
            j += 1;
          }
          i += 1;
        }
        k += 1;
      }
      i = 0;
      while (i < self.size) {

        j = 0;
        while (j < self.size) {
          if (Int.max == result[i][j]) {
            print(" INF ", terminator: "");
          } else {
            print(" ", result[i][j] ," ", terminator: "");
          }
          j += 1;
        }
        print("\n", terminator: "");
        i += 1;
      }
    } else {
      print("Empty Graph", terminator: "");
    }
  }
}
func main() {
  
  //5 implies the number of nodes in graph
  let g: MyGraph? = MyGraph(5);
  //First two parameter indicates number start and last nodes
  //And third parameter indicates weight of edge
  //Connected two node with Edges
  g!.add_edge(0, 1, 5);
  g!.add_edge(0, 2, 8);
  g!.add_edge(0, 4, 3);
  g!.add_edge(1, 4, 2);
  g!.add_edge(2, 1, 11);
  // When have 2 paths in same node with different weight
  // In real world scenario
  g!.add_edge(3, 0, 4);
  g!.add_edge(3, 0, 5);
  g!.add_edge(3, 2, 7);
  g!.add_edge(3, 4, 9);
  g!.add_edge(4, 2, 5);
  g!.print_graph();
  g!.floyd_warshall();
}
main();

Output

Adjacency list of vertex  0  :  1  2  4
Adjacency list of vertex  1  :  4
Adjacency list of vertex  2  :  1
Adjacency list of vertex  3  :  0  0  2  4
Adjacency list of vertex  4  :  2
  0    5    8   INF   3  
 INF   0    7   INF   2  
 INF   11    0   INF   13  
  4    9    7    0    7  
 INF   16    5   INF   0
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment