Skip to main content

Show path in Bellman Ford algorithm

Here given code implementation process.

//C Program
//Show path in 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)
  {

    // create Adjacency node
    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
      {
        //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->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 view_path(int path[], int location) 
  { 


    if (path[location] == - 1) 
    {

      return; 
    }
    
    view_path(path, path[location]); 
    
    printf("%d ", location); 
  }
  void bellman_ford(struct Graph*root,int source)
  {

    if(root!=NULL)
    {

      int distance[size],path[size];

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

        path[i]=-1;

      }

      distance[source] = 0;

      struct AjlistNode *temp=NULL;

      printf("\n Source node : %d\n",source );

      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;
              path[temp->vId]=j;
            }
            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 \tDistance Path\n");

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

          
        }

        view_path(path,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

      add_edge(node,0, 1, 5); 
      add_edge(node,0, 2, -3); 
      add_edge(node,0, 4, 3); 
      add_edge(node,1, 4, 5); 
      add_edge(node,2, 1, -5); 
      add_edge(node,3, 0, 4); 
      add_edge(node,3, 2, 6); 
      add_edge(node,3, 4, 9); 
      add_edge(node,4, 2, 5); 

      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
 Source node : 3

Vertex 	Distance Path

 0 	 4	 3 0
 1 	 -4	 3 0 2 1
 2 	 1	 3 0 2
 3 	 0	 3
 4 	 1	 3 0 2 1 4
// C++ program
// Show path in Bellman Ford algorithm
#include<iostream>
#include <limits.h> 
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;
			}
			//Add node 
			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 view_path(int path[], int location) {
		if (path[location] == -1) {
			return;
		}
		this->view_path(path, path[location]);
		cout << " " << location;
	}
	void bellman_ford(int source) {
		if (source < 0 &&
			source >= this->size) {
			return;
		}
		if (this->node != NULL) {
			int *distance = new int[size];
			int *path = new int[size];
			for (int i = 0; i < this->size; ++i) {
				//Initial distance is Integer.MAX_VALUE is infinity
				distance[i] = INT_MAX;
				path[i] = -1;
			}
			distance[source] = 0;
			AjlistNode *temp = NULL;
			cout << "\n Source Node " << source << " \n";
			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;
							path[temp->id] = j;
						}
						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 Path\n";
			for (int i = 0; i < this->size; ++i) {
				if (distance[i] == INT_MAX) {
					cout << " " << i << " \t \t Integer MAX VALUE\n";
				} else {
					cout << " " << i << " \t " << distance[i] << "\t " << source;
				}
				this->view_path(path, i);
				cout << "\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.add_edge(0, 1, 5);
	g.add_edge(0, 2, -3);
	g.add_edge(0, 4, 3);
	g.add_edge(1, 4, 5);
	g.add_edge(2, 1, -5);
	g.add_edge(3, 0, 4);
	g.add_edge(3, 2, 6);
	g.add_edge(3, 4, 9);
	g.add_edge(4, 2, 5);
	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
 Source Node 3

Vertex Distance Path
 0 	 4	 3 0
 1 	 -4	 3 0 2 1
 2 	 1	 3 0 2
 3 	 0	 3
 4 	 1	 3 0 2 1 4
// Java program
// Show path in 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;
      }
      //Add node 
      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++;
      }
    }
  }
  public void view_path(int []path, int location) 
  { 


    if (path[location] == - 1) 
    {

      return; 
    }
    
    view_path(path, path[location]); 
    
    System.out.print("  "+ location); 
  }
  public void bellman_ford(int source) {
    if (source < 0 && source >= this.size) {
      return;
    }
    if (node != null) {

      int[] distance = new int[size];

      int []path = new int[size];

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

      distance[source] = 0;

      AjlistNode temp = null;
      System.out.print("\n Source Node "+ source +" \n");

      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;
              path[temp.id]=j;
            }
            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    Path\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  " + distance[i] +"\t   "+source);
        }
        view_path(path,i);
        System.out.print("\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.add_edge(0, 1, 5);
    g.add_edge(0, 2, -3);
    g.add_edge(0, 4, 3);
    g.add_edge(1, 4, 5);
    g.add_edge(2, 1, -5);
    g.add_edge(3, 0, 4);
    g.add_edge(3, 2, 6);
    g.add_edge(3, 4, 9);
    g.add_edge(4, 2, 5);
    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
 Source Node 3

Vertex Distance Path
 0 	 4	 3 0
 1 	 -4	 3 0 2 1
 2 	 1	 3 0 2
 3 	 0	 3
 4 	 1	 3 0 2 1 4
// C# program
// Show path in Bellman Ford algorithm
using System;
public 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;
	}
}
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
	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;
			}
			//Add node 
			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++;
			}
		}
	}
	public void view_path(int[] path, int location) {
		if (path[location] == -1) {
			return;
		}
		view_path(path, path[location]);
		Console.Write(" " + location);
	}
	public void bellman_ford(int source) {
		if (source < 0 &&
			source >= this.size) {
			return;
		}
		if (node != null) {
			int[] distance = new int[size];
			int[] path = new int[size];
			for (int i = 0; i < size; ++i) {
				//Initial distance is Integer.MAX_VALUE is infinity
				distance[i] = int.MaxValue;
				path[i] = -1;
			}
			distance[source] = 0;
			AjlistNode temp = null;
			Console.Write("\n Source Node " + source + " \n");
			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;
							path[temp.id] = j;
						}
						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 Path\n");
			for (int i = 0; i < size; ++i) {
				if (distance[i] == int.MaxValue) {
					Console.Write(" " + i + " \t \t Integer MAX VALUE\n");
				} else {
					Console.Write(" " + i + " \t " + distance[i] + "\t " + source);
				}
				view_path(path, i);
				Console.Write("\n");
			}
		} else {
			Console.Write("Empty Graph");
		}
	}
	public static void Main(String[] args) {
		//Number of nodes
		int totalNode = 5;
		MyGraph g = new MyGraph(totalNode);
		g.add_edge(0, 1, 5);
		g.add_edge(0, 2, -3);
		g.add_edge(0, 4, 3);
		g.add_edge(1, 4, 5);
		g.add_edge(2, 1, -5);
		g.add_edge(3, 0, 4);
		g.add_edge(3, 2, 6);
		g.add_edge(3, 4, 9);
		g.add_edge(4, 2, 5);
		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
 Source Node 3

Vertex Distance Path
 0 	 4	 3 0
 1 	 -4	 3 0 2 1
 2 	 1	 3 0 2
 3 	 0	 3
 4 	 1	 3 0 2 1 4
<?php
// Php program
// Show path in 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, null);
		//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;
			}
			//Add node 
			$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++;
			}
		}
	}
	public 	function view_path( & $path, $location) {
		if ($path[$location] == -1) {
			return;
		}
		$this->view_path($path, $path[$location]);
		echo(" ". $location);
	}
	public 	function bellman_ford($source) {
		if ($source < 0 &&
			$source >= $this->size) {
			return;
		}
		if ($this->node != null) {
			$distance = array_fill(0, $this->size, 0);
			$path = array_fill(0, $this->size, 0);
			for ($i = 0; $i < $this->size; ++$i) {
				//Initial distance is Integer.MAX_VALUE is infinity
				$distance[$i] = PHP_INT_MAX;
				$path[$i] = -1;
			}
			$distance[$source] = 0;
			$temp = null;
			echo("\n Source Node ". $source ." \n");
			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;
							$path[$temp->id] = $j;
						}
						$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 Path\n");
			for ($i = 0; $i < $this->size; ++$i) {
				if ($distance[$i] == PHP_INT_MAX) {
					echo(" ". $i ." \t \t Integer MAX VALUE\n");
				} else {
					echo(" ". $i ." \t ". $distance[$i] ."\t ". $source);
				}
				$this->view_path($path, $i);
				echo("\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->add_edge(0, 1, 5);
	$g->add_edge(0, 2, -3);
	$g->add_edge(0, 4, 3);
	$g->add_edge(1, 4, 5);
	$g->add_edge(2, 1, -5);
	$g->add_edge(3, 0, 4);
	$g->add_edge(3, 2, 6);
	$g->add_edge(3, 4, 9);
	$g->add_edge(4, 2, 5);
	$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
 Source Node 3

Vertex Distance Path
 0 	 4	 3 0
 1 	 -4	 3 0 2 1
 2 	 1	 3 0 2
 3 	 0	 3
 4 	 1	 3 0 2 1 4
// Node Js program
// Show path in 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(null);
		//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
	add_edge(start, last, weight) {
		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;
			}

			//Add node 
			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++;
			}
		}
	}
	view_path(path, location) {
		if (path[location] == -1) {
			return;
		}
		this.view_path(path, path[location]);
		process.stdout.write(" " + location);
	}
	bellman_ford(source) {
		if (source < 0 &&
			source >= this.size) {
			return;
		}

		if (this.node != null) {
			var distance = Array(this.size).fill(0);
			var path = Array(this.size).fill(0);
			for (var i = 0; i < this.size; ++i) {
				//Initial distance is Integer.MAX_VALUE is infinity
				distance[i] = Number.MAX_VALUE;
				path[i] = -1;
			}
			distance[source] = 0;
			var temp = null;
			process.stdout.write("\n Source Node " + source + " \n");
			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;
							path[temp.id] = j;
						}
						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 Path\n");
			for (var i = 0; i < this.size; ++i) {
				if (distance[i] == Number.MAX_VALUE) {
					process.stdout.write(" " + i + " \t \t Integer MAX VALUE\n");
				} else {
					process.stdout.write(" " + i + " \t " + distance[i] + "\t " + source);
				}
				this.view_path(path, i);
				process.stdout.write("\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.add_edge(0, 1, 5);
	g.add_edge(0, 2, -3);
	g.add_edge(0, 4, 3);
	g.add_edge(1, 4, 5);
	g.add_edge(2, 1, -5);
	g.add_edge(3, 0, 4);
	g.add_edge(3, 2, 6);
	g.add_edge(3, 4, 9);
	g.add_edge(4, 2, 5);
	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
 Source Node 3

Vertex Distance Path
 0 	 4	 3 0
 1 	 -4	 3 0 2 1
 2 	 1	 3 0 2
 3 	 0	 3
 4 	 1	 3 0 2 1 4
#  Python 3 program
#  Show path in Bellman Ford algorithm
import sys
class AjlistNode :
	# Vertices node key
	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 = [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 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
			
			# Add node 
			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 view_path(self, path, location) :
		if (path[location] == -1) :
			return
		
		self.view_path(path, path[location])
		print(" ", location, end = "")
	
	def bellman_ford(self, source) :
		if (source < 0 and source >= self.size) :
			return
		
		if (self.node != None) :
			distance = [0] * self.size
			path = [0] * self.size
			i = 0
			while (i < self.size) :
				# Initial distance is Integer.MAX_VALUE is infinity
				distance[i] = sys.maxsize
				path[i] = -1
				i += 1
			
			distance[source] = 0
			temp = None
			print("\n Source Node ", source ," \n", end = "")
			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
							path[temp.id] = j
						
						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 Path\n", end = "")
			i = 0
			while (i < self.size) :
				if (distance[i] == sys.maxsize) :
					print(" ", i ," \t \t Integer MAX VALUE\n", end = "")
				else :
					print(" ", i ," \t ", distance[i] ,"\t ", source, end = "")
				
				self.view_path(path, i)
				print("\n", end = "")
				i += 1
			
		else :
			print("Empty Graph", end = "")
		
	

def main() :
	# Number of nodes
	totalNode = 5
	g = MyGraph(totalNode)
	# Connected two node with Edges
	# Third parameter is weight
	g.add_edge(0, 1, 5)
	g.add_edge(0, 2, -3)
	g.add_edge(0, 4, 3)
	g.add_edge(1, 4, 5)
	g.add_edge(2, 1, -5)
	g.add_edge(3, 0, 4)
	g.add_edge(3, 2, 6)
	g.add_edge(3, 4, 9)
	g.add_edge(4, 2, 5)
	g.print_graph()
	# Start location
	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
 Source Node  3

Vertex Distance Path
  0  	  4 	  3  0
  1  	  -4 	  3  0  2  1
  2  	  1 	  3  0  2
  3  	  0 	  3
  4  	  1 	  3  0  2  1  4
#  Ruby program
#  Show path in Bellman Ford algorithm
class AjlistNode
    # Define the accessor and reader of class AjlistNode
    attr_reader :id, :next, :weight
    attr_accessor :id, :next, :weight 
	# Vertices node key
	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_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) 
		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 node
	def add_edge(start, last, weight) 
		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
			# Add node 
			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 view_path(path, location) 
		if (path[location] == -1) 
			return
		end
		self.view_path(path, path[location])
		print(" ", location)
	end
	def bellman_ford(source) 
		if (source < 0 &&
			source >= self.size) 
			return
		end
		if (@node != nil) 
			distance = Array.new(@size) {0}
			path = Array.new(@size) {0}
			i = 0
			while (i < @size) 
				# Initial distance is Integer.MAX_VALUE is infinity
				distance[i] = (2 ** (0. size * 8 - 2))
				path[i] = -1
				i += 1
			end
			distance[source] = 0
			temp = nil
			print("\n Source Node ", source ," \n")
			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
							path[temp.id] = j
						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 Path\n")
			i = 0
			while (i < @size) 
				if (distance[i] == (2 ** (0. size * 8 - 2))) 
					print(" ", i ," \t \t Integer MAX VALUE\n")
				else 
					print(" ", i ," \t\t", distance[i] ,"\t\t  ", source)
				end
				self.view_path(path, i)
				print("\n")
				i += 1
			end
		else 
			print("Empty Graph")
		end
	end
end
def main() 
	# Number of nodes
	totalNode = 5
	g = MyGraph.new(totalNode)
	# Connected two node with Edges
	# Third parameter is weight
	g.add_edge(0, 1, 5)
	g.add_edge(0, 2, -3)
	g.add_edge(0, 4, 3)
	g.add_edge(1, 4, 5)
	g.add_edge(2, 1, -5)
	g.add_edge(3, 0, 4)
	g.add_edge(3, 2, 6)
	g.add_edge(3, 4, 9)
	g.add_edge(4, 2, 5)
	g.print_graph()
	# Start location
	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 
 Source Node 3 

Vertex Distance Path
 0 		4		  3 0
 1 		-4		  3 0 2 1
 2 		1		  3 0 2
 3 		0		  3
 4 		1		  3 0 2 1 4

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 (node(start).next == null) {
			//Include first adjacency list node of location start 
			node(start).next = newEdge;
		} else {
			var temp: AjlistNode = node(start).next;

			//Add new node at the end of edge
			while (temp.next != null) {
				temp = temp.next;
			}
			//Add node 
			temp.next = newEdge;
		}
	}
	//Display graph elements
	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;
			}
		}
	}
	def view_path(path: Array[Int], location: Int): Unit = {
		if (path(location) == -1) {
			return;
		}
		view_path(path, path(location));
		print(" " + location);
	}
	def bellman_ford(source: Int ): Unit = {
		if (source < 0 &&
			source >= this.size) {
			return;
		}
		if (node != null) {
			var distance: Array[Int] = Array.fill[Int](this.size)(0);
			var path: Array[Int] = Array.fill[Int](this.size)(0);
			var i: Int = 0;
			while (i < size) {
				//Initial distance is Integer.MAX_VALUE is infinity
				distance(i) = Int.MaxValue;
				path(i) = -1;
				i += 1;
			}
			distance(source) = 0;
			var temp: AjlistNode = null;
			print("\n Source Node " + source + " \n");
			i = 1;
          	var j: Int = 0;
			while (i < size) {
				j = 0;
				while (j < size) {
					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;
							path(temp.id) = j;
						}
						temp = temp.next;
					}
					j += 1;
				}
				i += 1;
			}
			i = 1;
			while (i < size) {
				j = 0;
				while (j < size) {
					temp = 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 Path\n");
			i = 0;
			while (i < size) {
				if (distance(i) == Int.MaxValue) {
					print(" " + i + " \t \t Integer MAX VALUE\n");
				} else {
					print(" " + i + " \t " + distance(i) + "\t " + source);
				}
				view_path(path, i);
				print("\n");
				i += 1;
			}
		} else {
			print("Empty Graph");
		}
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		//Number of nodes
		var totalNode: Int = 5;
		var g: MyGraph = new MyGraph(totalNode);

		//Connected two node with Edges
		//Third parameter is weight
		g.add_edge(0, 1, 5);
		g.add_edge(0, 2, -3);
		g.add_edge(0, 4, 3);
		g.add_edge(1, 4, 5);
		g.add_edge(2, 1, -5);
		g.add_edge(3, 0, 4);
		g.add_edge(3, 2, 6);
		g.add_edge(3, 4, 9);
		g.add_edge(4, 2, 5);
		g.print_graph();

		//Start location
		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
 Source Node 3

Vertex Distance Path
 0 	 4	 3 0
 1 	 -4	 3 0 2 1
 2 	 1	 3 0 2
 3 	 0	 3
 4 	 1	 3 0 2 1 4
// Swift program
// Show path in 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;
        }
	}
	//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;
			}
			//Add node 
			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 view_path(_ path: [Int], _ location: Int) {
		if (path[location] == -1) {
			return;
		}
		self.view_path(path, path[location]);
		print(" ", location, terminator: "");
	}
	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 path: [Int] = Array(repeating: 0, count: self.size);
			var i: Int = 0;
			while (i < self.size) {
				//Initial distance is Integer.MAX_VALUE is infinity
				distance[i] = Int.max;
				path[i] = -1;
				i += 1;
			}
			distance[source] = 0;
			var temp: AjlistNode? = nil;
			print("\n Source Node ", source ," \n", terminator: "");
			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;
							path[temp!.id] = j;
						}
						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 Path\n", terminator: "");
			i = 0;
			while (i < self.size) {
				if (distance[i] == Int.max) {
					print(" ", i ," \t \t Integer MAX VALUE\n", terminator: "");
				} else {
					print(" ", i ," \t ", distance[i] ,"\t ", source, terminator: "");
				}
				self.view_path(path, i);
				print("\n", terminator: "");
				i += 1;
			}
		} else {
			print("Empty Graph", terminator: "");
		}
	}
}
func main() {
	//Number of nodes
	let totalNode: Int = 5;
	let g: MyGraph? = MyGraph(totalNode);
	//Connected two node with Edges
	//Third parameter is weight
	g!.add_edge(0, 1, 5);
	g!.add_edge(0, 2, -3);
	g!.add_edge(0, 4, 3);
	g!.add_edge(1, 4, 5);
	g!.add_edge(2, 1, -5);
	g!.add_edge(3, 0, 4);
	g!.add_edge(3, 2, 6);
	g!.add_edge(3, 4, 9);
	g!.add_edge(4, 2, 5);
	g!.print_graph();
	//Start location
	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
 Source Node  3

Vertex Distance Path
  0  	  4 	  3  0
  1  	  -4 	  3  0  2  1
  2  	  1 	  3  0  2
  3  	  0 	  3
  4  	  1 	  3  0  2  1  4
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