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