# Bellman Ford Algorithm

The Bellman-Ford algorithm is a graph algorithm used to find the shortest path between a source vertex and all other vertices in a weighted directed graph. It is similar to Dijkstra's algorithm, but it can handle graphs with negative edge weights.

The algorithm works by iteratively relaxing each edge in the graph, updating the shortest path estimate for each vertex until it has converged on the optimal solution. The process of relaxing an edge involves checking if the path to the destination vertex through the current vertex is shorter than the current shortest path estimate, and updating the estimate if it is.

If the graph contains a negative weight cycle, meaning that the sum of the weights along any cycle in the graph is negative, then the algorithm can detect it and report that no shortest path exists. Otherwise, the algorithm will return the shortest path from the source vertex to all other vertices in the graph.

The time complexity of the Bellman-Ford algorithm is O(VE), where V is the number of vertices in the graph and E is the number of edges.

Here given code implementation process.

``````//C Program
//Bellman Ford Algorithm
#include <stdio.h>

#include <stdlib.h>

#include <limits.h> //for INT_MAX

#define INF INT_MAX

struct AjlistNode {
int vId; //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) {

struct AjlistNode *newEdge = (struct AjlistNode *) malloc(
sizeof(struct AjlistNode)
);
if (newEdge != NULL) {

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

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

if (temp == NULL) {
node[V].next = newEdge;
} else {
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);
}
}
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->vId is graph node vertices
//in this case temp->vId is same as
//node[temp->vId].data

printf("  %d", node[temp->vId].data);
temp = temp->next;
}
}
} else {
printf("Empty Graph");
}
}

void bellman_ford(struct Graph *root, int source) {

if (root != NULL) {

int distance[size];

for (int i = 0; i < size; ++i) {
//Initial distance is infinity
distance[i] = INF;

}

distance[source] = 0;

struct AjlistNode *temp = NULL;

for (int i = 1; i < size; ++i) {

for (int j = 0; j < size; ++j) {
temp = root[j].next;
//compare node (J) outgoing edges
while (temp != NULL) {
if (distance[j] != INF && distance[j] + temp->weight < distance[temp->vId]) {
distance[temp->vId] = distance[j] + temp->weight;

}
temp = temp->next;
}
}
}

for (int i = 1; i < size; ++i) {

for (int j = 0; j < size; ++j) {
temp = root[j].next;

//compare node (J) outgoing edges
while (temp != NULL) {
if (distance[j] != INF && distance[j] + temp->weight < distance[temp->vId]) {
printf("\n Negative Cycle exist node (%d %d)\n", temp->vId, j);
return;

}
temp = temp->next;
}
}
}

printf("\nVertex   Distance Source Node (%d)\n", source);

for (int i = 0; i < size; ++i) {
if (distance[i] == INF) {
printf(" %d \t \t INF\n", i);
} else {
printf(" %d \t \t %d\n", i, distance[i]);
}

}

} 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
//Second and third parameter is connected edges
//and last is edge weight

print_graph(node);

bellman_ford(node, 3);

}
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  2  4
Adjacency list of vertex 4  :  2
Vertex   Distance Source Node (3)
0 	 	 4
1 	 	 -4
2 	 	 1
3 	 	 0
4 	 	 1``````
``````// C++ program
// Bellman Ford Algorithm
#include<iostream>
#include <limits.h> //for INT_MAX
using namespace std;
class AjlistNode {
public:

//Vertices node key
int id;
AjlistNode *next;
int weight;
AjlistNode(int id, int weight) {
//Set value of node key
this->id = id;
this->next = NULL;
this->weight = weight;
}
};
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) {
this->size = size;
this->node = new Vertices[size];
//set initial values of graph node
this->set_data();
}
//Set initial node value
void set_data() {
if (this->node == NULL) {
cout << "\nEmpty Graph";
} else {
int index = 0;
while (index < this->size) {
this->node[index] = index;
index++;
}
}
}
//Connect two node
void add_edge(int start, int last, int weight) {
AjlistNode *newEdge = new AjlistNode(last, weight);
if (this->node[start].next == NULL) {
//Include first adjacency list node of location start
this->node[start].next = newEdge;
} else {
AjlistNode *temp = this->node[start].next;
//Add new node at the end of edge
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newEdge;
}
}
//Display graph elements
void print_graph() {
if (this->size > 0 &&
this->node != NULL) {
int index = 0;
while (index < this->size) {
cout << "\nAdjacency list of vertex " << index << " : ";
AjlistNode *temp = this->node[index].next;
while (temp != NULL) {
cout << this->node[temp->id].data << " ";
temp = temp->next;
}
index++;
}
}
}
void bellman_ford(int source) {
if (source < 0 &&
source >= this->size) {
return;
}
if (this->node != NULL) {
int *distance = new int[size];
for (int i = 0; i < this->size; ++i) {
//Initial distance is INT_MAX is infinity
distance[i] = INT_MAX;
}
distance[source] = 0;
AjlistNode *temp = NULL;
for (int i = 1; i < this->size; ++i) {
for (int j = 0; j < this->size; ++j) {
temp = this->node[j].next;
//compare node (J) outgoing edges
while (temp != NULL) {
if (distance[j] != INT_MAX &&
distance[j] + temp->weight < distance[temp->id]) {
distance[temp->id] = distance[j] + temp->weight;
}
temp = temp->next;
}
}
}
for (int i = 1; i < this->size; ++i) {
for (int j = 0; j < this->size; ++j) {
temp = this->node[j].next;
//compare node (J) outgoing edges
while (temp != NULL) {
if (distance[j] != INT_MAX &&
distance[j] + temp->weight < distance[temp->id]) {
cout << "\n Negative Cycle exist node (" << temp->id << " " << j << ")\n";
return;
}
temp = temp->next;
}
}
}
cout << "\nVertex Distance Source Node (" << source << ")\n";
for (int i = 0; i < this->size; ++i) {
if (distance[i] == INT_MAX) {
cout << " " << i << " \t \t INT_MAX\n";
} else {
cout << " " << i << " \t \t " << distance[i] << "\n";
}
}
} else {
cout << "Empty Graph";
}
}
};
int main() {
//Number of nodes
int totalNode = 5;
MyGraph g =  MyGraph(totalNode);
//Connected two node with Edges
//Third parameter is weight
g.print_graph();
//Start location
int start = 3;
g.bellman_ford(start);
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 2 4
Adjacency list of vertex 4 : 2
Vertex Distance Source Node (3)
0 	 	 4
1 	 	 -4
2 	 	 1
3 	 	 0
4 	 	 1``````
``````// Java program
// Bellman Ford Algorithm

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

public int data;
public AjlistNode next;

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

public class MyGraph {

//number of Vertices
private int size;

private Vertices[] node;

public MyGraph(int size) {

this.size = size;

this.node = new Vertices[size];
//set initial values of graph node
this.set_data();

}

//Set initial node value
public void set_data() {
if (node == null) {
System.out.println("\nEmpty Graph");
} else {

int index = 0;

while (index < size) {

node[index] = new Vertices(index);

index++;
}
}
}

//Connect two node
public void add_edge(int start, int last, int weight) {

AjlistNode newEdge = new AjlistNode(last, weight);

if (node[start].next == null) {
//Include first adjacency list node of location start
node[start].next = newEdge;
} else {
AjlistNode temp = node[start].next;
//Add new node at the end of edge
while (temp.next != null) {
temp = temp.next;
}
temp.next = newEdge;
}
}
//Display graph elements
public void print_graph() {

if (size > 0 && node != null) {
int index = 0;
while (index < size) {
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;
}
index++;
}
}
}
void bellman_ford(int source) {
if (source < 0 && source >= this.size) {
return;
}
if (node != null) {

int[] distance = new int[size];

for (int i = 0; i < size; ++i) {
//Initial distance is Integer.MAX_VALUE is infinity
distance[i] = Integer.MAX_VALUE;

}

distance[source] = 0;

AjlistNode temp = null;

for (int i = 1; i < size; ++i) {

for (int j = 0; j < size; ++j) {
temp = node[j].next;
//compare node (J) outgoing edges
while (temp != null) {
if (distance[j] != Integer.MAX_VALUE && distance[j] + temp.weight < distance[temp.id]) {
distance[temp.id] = distance[j] + temp.weight;

}
temp = temp.next;
}
}
}

for (int i = 1; i < size; ++i) {

for (int j = 0; j < size; ++j) {
temp = node[j].next;

//compare node (J) outgoing edges
while (temp != null) {
if (distance[j] != Integer.MAX_VALUE && distance[j] + temp.weight < distance[temp.id]) {
System.out.print("\n Negative Cycle exist node (" + temp.id + " " + j + ")\n");
return;

}
temp = temp.next;
}
}
}

System.out.print("\nVertex   Distance Source Node (" + source + ")\n");

for (int i = 0; i < size; ++i) {
if (distance[i] == Integer.MAX_VALUE) {
System.out.print(" " + i + " \t \t Integer.MAX_VALUE\n");
} else {
System.out.print(" " + i + " \t \t " + distance[i] + "\n");
}

}

} else {
System.out.print("Empty Graph");
}
}

public static void main(String[] args) {
//Number of nodes
int totalNode = 5;

MyGraph g = new MyGraph(totalNode);
//Connected two node with Edges
//Third parameter is weight
g.print_graph();

//Start location
int start = 3;

g.bellman_ford(start);

}
} ```
```

#### 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  2  4
Adjacency list of vertex 4 : 2
Vertex   Distance Source Node (3)
0 	 	 4
1 	 	 -4
2 	 	 1
3 	 	 0
4 	 	 1
``````
``````// C# program
// Bellman Ford Algorithm
using System;
class AjlistNode {
//Vertices node key
public int id;
public AjlistNode next;
public int weight;
public AjlistNode(int id, int weight) {
//Set value of node key
this.id = id;
this.next = null;
this.weight = weight;
}
}
class Vertices {
public int data;
public AjlistNode next;
public Vertices(int data) {
this.data = data;
this.next = null;
}
}
public class MyGraph {
//number of Vertices
private int size;
private Vertices[] node;
public MyGraph(int size) {
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 {
int index = 0;
while (index < size) {
node[index] = new Vertices(index);
index++;
}
}
}
//Connect two node
public void add_edge(int start, int last, int weight) {
AjlistNode newEdge = new AjlistNode(last, weight);
if (node[start].next == null) {
//Include first adjacency list node of location start
node[start].next = newEdge;
} else {
AjlistNode temp = node[start].next;
//Add new node at the end of edge
while (temp.next != null) {
temp = temp.next;
}
temp.next = newEdge;
}
}
//Display graph elements
public void print_graph() {
if (size > 0 &&
node != null) {
int index = 0;
while (index < size) {
Console.Write("\nAdjacency list of vertex " + index + " : ");
AjlistNode temp = node[index].next;
while (temp != null) {
Console.Write(node[temp.id].data + " ");
temp = temp.next;
}
index++;
}
}
}
void bellman_ford(int source) {
if (source < 0 &&
source >= this.size) {
return;
}
if (node != null) {
int[] distance = new int[size];
for (int i = 0; i < size; ++i) {
//Initial distance is Integer MAX is infinity
distance[i] = int.MaxValue;
}
distance[source] = 0;
AjlistNode temp = null;
for (int i = 1; i < size; ++i) {
for (int j = 0; j < size; ++j) {
temp = node[j].next;
//compare node (J) outgoing edges
while (temp != null) {
if (distance[j] != int.MaxValue &&
distance[j] + temp.weight < distance[temp.id]) {
distance[temp.id] = distance[j] + temp.weight;
}
temp = temp.next;
}
}
}
for (int i = 1; i < size; ++i) {
for (int j = 0; j < size; ++j) {
temp = node[j].next;
//compare node (J) outgoing edges
while (temp != null) {
if (distance[j] != int.MaxValue &&
distance[j] + temp.weight < distance[temp.id]) {
Console.Write("\n Negative Cycle exist node (" + temp.id + " " + j + ")\n");
return;
}
temp = temp.next;
}
}
}
Console.Write("\nVertex Distance Source Node (" + source + ")\n");
for (int i = 0; i < size; ++i) {
if (distance[i] == int.MaxValue) {
Console.Write(" " + i + " \t \t Integer MAX\n");
} else {
Console.Write(" " + i + " \t \t " + distance[i] + "\n");
}
}
} else {
Console.Write("Empty Graph");
}
}
public static void Main(String[] args) {
//Number of nodes
int totalNode = 5;
MyGraph g = new MyGraph(totalNode);
g.print_graph();
//Start location
int start = 3;
g.bellman_ford(start);
}
}```
```

#### 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 2 4
Adjacency list of vertex 4 : 2
Vertex Distance Source Node (3)
0 	 	 4
1 	 	 -4
2 	 	 1
3 	 	 0
4 	 	 1``````
``````<?php
// Php program
// Bellman Ford Algorithm
class AjlistNode {
//Vertices node key

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

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

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

private \$size;
private \$node;

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

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

public 	function add_edge(\$start, \$last, \$weight) {
\$newEdge = new AjlistNode(\$last, \$weight);
if (\$this->node[\$start]->next == null) {
//Include first adjacency list node of location start
\$this->node[\$start]->next = \$newEdge;
} else {
\$temp = \$this->node[\$start]->next;
//Add new node at the end of edge
while (\$temp->next != null) {
\$temp = \$temp->next;
}
\$temp->next = \$newEdge;
}
}
//Display graph elements

public 	function print_graph() {
if (\$this->size > 0 &&
\$this->node != null) {
\$index = 0;
while (\$index < \$this->size) {
echo("\nAdjacency list of vertex ". \$index ." : ");
\$temp = \$this->node[\$index]->next;
while (\$temp != null) {
echo(\$this->node[\$temp->id]->data ." ");
\$temp = \$temp->next;
}
\$index++;
}
}
}

function bellman_ford(\$source) {
if (\$source < 0 &&
\$source >= \$this->size) {
return;
}
if (\$this->node != null) {
\$distance = array_fill(0, \$this->size, 0);
for (\$i = 0; \$i < \$this->size; ++\$i) {
//Initial distance is Integer MAX is infinity
\$distance[\$i] = PHP_INT_MAX;
}
\$distance[\$source] = 0;
\$temp = null;
for (\$i = 1; \$i < \$this->size; ++\$i) {
for (\$j = 0; \$j < \$this->size; ++\$j) {
\$temp = \$this->node[\$j]->next;
//compare node (J) outgoing edges
while (\$temp != null) {
if (\$distance[\$j] != PHP_INT_MAX &&
\$distance[\$j] + \$temp->weight < \$distance[\$temp->id]) {
\$distance[\$temp->id] = \$distance[\$j] + \$temp->weight;
}
\$temp = \$temp->next;
}
}
}
for (\$i = 1; \$i < \$this->size; ++\$i) {
for (\$j = 0; \$j < \$this->size; ++\$j) {
\$temp = \$this->node[\$j]->next;
//compare node (J) outgoing edges
while (\$temp != null) {
if (\$distance[\$j] != PHP_INT_MAX &&
\$distance[\$j] + \$temp->weight < \$distance[\$temp->id]) {
echo("\n Negative Cycle exist node (". \$temp->id ." ". \$j .")\n");
return;
}
\$temp = \$temp->next;
}
}
}
echo("\nVertex Distance Source Node (". \$source .")\n");
for (\$i = 0; \$i < \$this->size; ++\$i) {
if (\$distance[\$i] == PHP_INT_MAX) {
echo(" ". \$i ." \t \t Integer MAX\n");
} else {
echo(" ". \$i ." \t \t ". \$distance[\$i] ."\n");
}
}
} else {
echo("Empty Graph");
}
}
}

function main() {
//Number of nodes
\$totalNode = 5;
\$g = new MyGraph(\$totalNode);
//Connected two node with Edges
//Third parameter is weight
\$g->print_graph();
//Start location
\$start = 3;
\$g->bellman_ford(\$start);

}
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 2 4
Adjacency list of vertex 4 : 2
Vertex Distance Source Node (3)
0 	 	 4
1 	 	 -4
2 	 	 1
3 	 	 0
4 	 	 1``````
``````// Node Js program
// Bellman Ford Algorithm
class AjlistNode {
//Vertices node key

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

constructor(size) {
this.size = size;
this.node = Array(size).fill(0);
//set initial values of graph node
this.set_data();
}

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

//Connect two node
var newEdge = new AjlistNode(last, weight);
if (this.node[start].next == null) {
//Include first adjacency list node of location start
this.node[start].next = newEdge;
} else {
var temp = this.node[start].next;
//Add new node at the end of edge
while (temp.next != null) {
temp = temp.next;
}

temp.next = newEdge;
}
}

//Display graph elements
print_graph() {
if (this.size > 0 &&
this.node != null) {
var index = 0;
while (index < this.size) {
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;
}
index++;
}
}
}
bellman_ford(source) {
if (source < 0 &&
source >= this.size) {
return;
}

if (this.node != null) {
var distance = Array(this.size).fill(0);
for (var i = 0; i < this.size; ++i) {
//Initial distance is Integer MAX is infinity
distance[i] = Number.MAX_VALUE;
}
distance[source] = 0;
var temp = null;
for (var i = 1; i < this.size; ++i) {
for (var j = 0; j < this.size; ++j) {
temp = this.node[j].next;
//compare node (J) outgoing edges
while (temp != null) {
if (distance[j] != Number.MAX_VALUE &&
distance[j] + temp.weight < distance[temp.id]) {
distance[temp.id] = distance[j] + temp.weight;
}
temp = temp.next;
}
}
}

for (var i = 1; i < this.size; ++i) {
for (var j = 0; j < this.size; ++j) {
temp = this.node[j].next;
//compare node (J) outgoing edges
while (temp != null) {
if (distance[j] != Number.MAX_VALUE &&
distance[j] + temp.weight < distance[temp.id]) {
process.stdout.write("\n Negative Cycle exist node (" + temp.id + " " + j + ")\n");
return;
}
temp = temp.next;
}
}
}

process.stdout.write("\nVertex Distance Source Node (" + source + ")\n");
for (var i = 0; i < this.size; ++i) {
if (distance[i] == Number.MAX_VALUE) {
process.stdout.write(" " + i + " \t \t Integer MAX\n");
} else {
process.stdout.write(" " + i + " \t \t " + distance[i] + "\n");
}
}
} else {
process.stdout.write("Empty Graph");
}
}
}

function main(args) {
//Number of nodes
var totalNode = 5;
var g = new MyGraph(totalNode);
//Connected two node with Edges
//Third parameter is weight
g.print_graph();
//Start location
var start = 3;
g.bellman_ford(start);
}

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 2 4
Adjacency list of vertex 4 : 2
Vertex Distance Source Node (3)
0 	 	 4
1 	 	 -4
2 	 	 1
3 	 	 0
4 	 	 1``````
``````#  Python 3 program
#  Bellman Ford Algorithm
import sys
class AjlistNode :

def __init__(self, id, weight) :
# Set value of node key
self.id = id
self.next = None
self.weight = weight

class Vertices :

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

class MyGraph :
# number of Vertices

def __init__(self, size) :
self.size = size
self.node = [0] * 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 node
def add_edge(self, start, last, weight) :
newEdge = AjlistNode(last, weight)
if (self.node[start].next == None) :
# Include first adjacency list node of location start
self.node[start].next = newEdge
else :
temp = self.node[start].next
# Add new node at the end of edge
while (temp.next != None) :
temp = temp.next

temp.next = newEdge

# Display graph elements
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

def bellman_ford(self, source) :
if (source < 0 and source >= self.size) :
return

if (self.node != None) :
distance = [0] * self.size
i = 0
while (i < self.size) :
# Initial distance is Integer MAX is infinity
distance[i] = sys.maxsize
i += 1

distance[source] = 0
temp = None
i = 1
while (i < self.size) :
j = 0
while (j < self.size) :
temp = self.node[j].next
# compare node (J) outgoing edges
while (temp != None) :
if (distance[j] != sys.maxsize and distance[j] + temp.weight < distance[temp.id]) :
distance[temp.id] = distance[j] + temp.weight

temp = temp.next

j += 1

i += 1

i = 1
while (i < self.size) :
j = 0
while (j < self.size) :
temp = self.node[j].next
# compare node (J) outgoing edges
while (temp != None) :
if (distance[j] != sys.maxsize and distance[j] + temp.weight < distance[temp.id]) :
print("\n Negative Cycle exist node (", temp.id ," ", j ,")\n", end = "")
return

temp = temp.next

j += 1

i += 1

print("\nVertex Distance Source Node (", source ,")\n", end = "")
i = 0
while (i < self.size) :
if (distance[i] == sys.maxsize) :
print(" ", i ," \t \t Integer MAX\n", end = "")
else :
print(" ", i ," \t \t ", distance[i] ,"\n", end = "")

i += 1

else :
print("Empty Graph", end = "")

def main() :
totalNode = 5
g = MyGraph(totalNode)
g.print_graph()
start = 3
g.bellman_ford(start)

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  2  4
Adjacency list of vertex  4  : 2
Vertex Distance Source Node ( 3 )
0  	 	  4
1  	 	  -4
2  	 	  1
3  	 	  0
4  	 	  1``````
``````#  Ruby program
#  Bellman Ford Algorithm
class AjlistNode
# Define the accessor and reader of class AjlistNode
attr_accessor :id, :next, :weight

def initialize(id, weight)
# Set value of node key
self.id = id
self.next = nil
self.weight = weight
end
end
class Vertices
# Define the accessor and reader of class Vertices
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_accessor :size, :node

def initialize(size)
self.size = size
self.node = Array.new(size) {0}
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 node
newEdge = AjlistNode.new(last, weight)
if (@node[start].next == nil)
# Include first adjacency list node of location start
@node[start].next = newEdge
else
temp = @node[start].next
# Add new node at the end of edge
while (temp.next != nil)
temp = temp.next
end
temp.next = newEdge
end
end
# Display graph elements
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
def bellman_ford(source)
if (source < 0 &&
source >= self.size)
return
end
if (@node != nil)
distance = Array.new(@size) {0}
i = 0
while (i < @size)
# Initial distance is Integer MAX is infinity
distance[i] = (2 ** (0. size * 8 - 2))
i += 1
end
distance[source] = 0
temp = nil
i = 1
while (i < @size)
j = 0
while (j < @size)
temp = @node[j].next
# compare node (J) outgoing edges
while (temp != nil)
if (distance[j] != (2 ** (0. size * 8 - 2)) &&
distance[j] + temp.weight < distance[temp.id])
distance[temp.id] = distance[j] + temp.weight
end
temp = temp.next
end
j += 1
end
i += 1
end
i = 1
while (i < @size)
j = 0
while (j < @size)
temp = @node[j].next
# compare node (J) outgoing edges
while (temp != nil)
if (distance[j] != (2 ** (0. size * 8 - 2)) &&
distance[j] + temp.weight < distance[temp.id])
print("\n Negative Cycle exist node (", temp.id ," ", j ,")\n")
return
end
temp = temp.next
end
j += 1
end
i += 1
end
print("\nVertex Distance Source Node (", source ,")\n")
i = 0
while (i < @size)
if (distance[i] == (2 ** (0. size * 8 - 2)))
print(" ", i ," \t \t Integer MAX\n")
else
print(" ", i ," \t \t ", distance[i] ,"\n")
end
i += 1
end
else
print("Empty Graph")
end
end
end
def main()
totalNode = 5
g = MyGraph.new(totalNode)
g.print_graph()
start = 3
g.bellman_ford(start)
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 2 4
Adjacency list of vertex 4  : 2
Vertex Distance Source Node (3)
0 	 	 4
1 	 	 -4
2 	 	 1
3 	 	 0
4 	 	 1
``````
``````// Scala program
// Bellman Ford 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]) {
def this(value: Int) {
//set value
this(value,Array.fill[Vertices](value)(null));
//set initial values of graph node
this.set_data();
}

//Set initial node value
def set_data(): Unit = {
if (this.node == null) {
print("\nEmpty Graph");
} else {
var index: Int = 0;
while (index < this.size) {
this.node(index) = new Vertices(index);
index += 1;
}
}
}
//Connect two node
def add_edge(start: Int, last: Int, weight: Int): Unit = {
var newEdge: AjlistNode = new AjlistNode(last, weight);

if (this.node(start).next == null) {
//Include first adjacency list node of location start
this.node(start).next = newEdge;
} else {
var temp: AjlistNode = this.node(start).next;

//Add new node at the end of edge
while (temp.next != null) {
temp = temp.next;
}
temp.next = newEdge;
}
}
//Display graph elements
def print_graph(): Unit = {
if (this.size > 0 &&
this.node != null) {
var index: Int = 0;
while (index < this.size) {
print("\nAdjacency list of vertex " + index + " : ");
var temp: AjlistNode = this.node(index).next;
while (temp != null) {
print(""+this.node(temp.id).data + " ");
temp = temp.next;
}
index += 1;
}
}
}
def bellman_ford(source: Int): Unit = {
if (source < 0 &&
source >= this.size) {
return;
}
if (this.node != null) {
var distance: Array[Int] = Array.fill[Int](this.size)(0);
var i: Int = 0;
while (i < this.size) {
//Initial distance is Integer MAX is infinity
distance(i) = Int.MaxValue;
i += 1;
}
distance(source) = 0;
var temp: AjlistNode = null;
i = 1;
var j: Int = 0;
while (i < this.size) {
j = 0;
while (j < this.size) {
temp = this.node(j).next;

//compare node (J) outgoing edges
while (temp != null) {
if (distance(j) != Int.MaxValue &&
distance(j) + temp.weight < distance(temp.id)) {
distance(temp.id) = distance(j) + temp.weight;
}
temp = temp.next;
}
j += 1;
}
i += 1;
}
i = 1;
while (i < this.size) {
j = 0;
while (j < this.size) {
temp = this.node(j).next;

//compare node (J) outgoing edges
while (temp != null) {
if (distance(j) != Int.MaxValue &&
distance(j) + temp.weight < distance(temp.id)) {
print("\n Negative Cycle exist node (" + temp.id + " " + j + ")\n");

return;
}
temp = temp.next;
}
j += 1;
}
i += 1;
}
print("\nVertex Distance Source Node (" + source + ")\n");
i = 0;
while (i < this.size) {
if (distance(i) == Int.MaxValue) {
print(" " + i + " \t \t Integer MAX\n");
} else {
print(" " + i + " \t \t " + distance(i) + "\n");
}
i += 1;
}
} else {
print("Empty Graph");
}
}
}
object Main {
def main(args: Array[String]): Unit = {
var totalNode: Int = 5;
var g: MyGraph = new MyGraph(totalNode);
g.print_graph();
var start: Int = 3;
g.bellman_ford(start);
}
}```
```

#### 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 2 4
Adjacency list of vertex 4 : 2
Vertex Distance Source Node (3)
0 	 	 4
1 	 	 -4
2 	 	 1
3 	 	 0
4 	 	 1``````
``````// Swift program
// Bellman Ford Algorithm
class AjlistNode {
//Vertices node key
var id: Int;
var next: AjlistNode? ;
var weight: Int;
init(_ id: Int, _ weight: Int) {
//Set value of node key
self.id = id;
self.next = nil;
self.weight = weight;
}
}
class Vertices {
var data: Int;
var next: AjlistNode? ;
init(_ data: Int) {
self.data = data;
self.next = nil;
}
}
class MyGraph {
//number of Vertices
var size: Int;
var node: [Vertices]? = [Vertices]() ;
init(_ size: Int) {
self.size = size;
var i = 0;
while (i<size) {
self.node!.append(Vertices(i));
i+=1;
}
}
//Set initial node value
func set_data() {
if (self.node == nil) {
print("\nEmpty Graph", terminator: "");
} else {
var index: Int = 0;
while (index < self.size) {
self.node![index] = Vertices(index);
index += 1;
}
}
}
//Connect two node
func add_edge(_ start: Int, _ last: Int, _ weight: Int) {
let newEdge: AjlistNode? = AjlistNode(last, weight);
if (self.node![start].next == nil) {
//Include first adjacency list node of location start
self.node![start].next = newEdge;
} else {
var temp: AjlistNode? = self.node![start].next;
//Add new node at the end of edge
while (temp!.next != nil) {
temp = temp!.next;
}
temp!.next = newEdge;
}
}
//Display graph elements
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;
}
}
}
func bellman_ford(_ source: Int) {
if (source < 0 &&
source >= self.size) {
return;
}
if (self.node != nil) {
var distance: [Int] = Array(repeating: 0, count: self.size);
var i: Int = 0;
while (i < self.size) {
//Initial distance is Integer MAX is infinity
distance[i] = Int.max;
i += 1;
}
distance[source] = 0;
var temp: AjlistNode? = nil;
i = 1;
var j: Int = 0;
while (i < self.size) {
j = 0;
while (j < self.size) {
temp = self.node![j].next;
//compare node (J) outgoing edges
while (temp != nil) {
if (distance[j] != Int.max &&
distance[j] + temp!.weight < distance[temp!.id]) {
distance[temp!.id] = distance[j] + temp!.weight;
}
temp = temp!.next;
}
j += 1;
}
i += 1;
}
i = 1;
while (i < self.size) {
j = 0;
while (j < self.size) {
temp = self.node![j].next;
//compare node (J) outgoing edges
while (temp != nil) {
if (distance[j] != Int.max &&
distance[j] + temp!.weight < distance[temp!.id]) {
print("\n Negative Cycle exist node (", temp!.id ," ", j ,")\n", terminator: "");
return;
}
temp = temp!.next;
}
j += 1;
}
i += 1;
}
print("\nVertex Distance Source Node (", source ,")\n", terminator: "");
i = 0;
while (i < self.size) {
if (distance[i] == Int.max) {
print(" ", i ," \t \t Integer MAX\n", terminator: "");
} else {
print(" ", i ," \t \t ", distance[i] ,"\n", terminator: "");
}
i += 1;
}
} else {
print("Empty Graph", terminator: "");
}
}
}
func main() {
let totalNode: Int = 5;
let g: MyGraph? = MyGraph(totalNode);
g!.print_graph();
let start: Int = 3;
g!.bellman_ford(start);
}
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  2  4
Adjacency list of vertex  4  : 2
Vertex Distance Source Node ( 3 )
0  	 	  4
1  	 	  -4
2  	 	  1
3  	 	  0
4  	 	  1``````

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