Posted on by Kalkicode
Code Algorithm

Understanding the Bellman-Ford Algorithm and Showing the Shortest Path

The Bellman-Ford algorithm is a widely used graph traversal algorithm that is used to find the shortest path from a source node to all other nodes in a weighted graph. It is particularly useful when dealing with graphs that may contain negative weight edges. In this article, we will explore the Bellman-Ford algorithm and provide a step-by-step explanation of the code provided.

What is the Bellman-Ford Algorithm?

The Bellman-Ford algorithm is an algorithm that solves the single-source shortest path problem in a weighted directed graph. It can handle graphs with negative weight edges and detects negative cycles. The algorithm maintains a distance array, where each element represents the minimum distance from the source node to that particular node.

Code Solution

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

Understanding the Code:

The provided code is an implementation of the Bellman-Ford algorithm in C. Let's break down the code into its main components:

Data Structures:

  • struct AjlistNode: Represents a node in the adjacency list. It contains the ID of the connected vertex and the weight of the edge.
  • struct Graph: Represents a graph. It contains a data field (node key value) and a pointer to the first node in the adjacency list.

Functions:

  • set_data: Sets the data (node key value) for each node in the graph.
  • connect_edge: Connects two nodes by creating an adjacency node and adding it to the adjacency list.
  • add_edge: Adds an edge between two given nodes with a specified weight.
  • print_graph: Prints the adjacency list representation of the graph.
  • view_path: Recursive function to view the shortest path from the source node to a given node.
  • bellman_ford: Implements the Bellman-Ford algorithm to find the shortest path from the source node to all other nodes.

Walkthrough of the Bellman-Ford Algorithm:

Now, let's understand how the Bellman-Ford algorithm works based on the provided code:

Initializing the Graph:
  • The size variable represents the number of nodes in the graph.
  • The set_data function is called to set the key value for each node in the graph.
Adding Edges:

The add_edge function is used to add edges between nodes along with their corresponding weights. This creates the adjacency list representation of the graph.

Bellman-Ford Algorithm:
  • The bellman_ford function implements the Bellman-Ford algorithm.
  • It initializes the distance array with infinity values except for the source node, which is set to 0.
  • The algorithm iterates size - 1 times to relax all the edges in the graph.
  • For each iteration, it checks all the outgoing edges from each node and updates the distance if a shorter path is found.
  • After the iterations, the algorithm performs one more pass to check for negative cycles. If a shorter path is found, it indicates the presence of a negative cycle.
  • Finally, the algorithm prints the vertex, its distance from the source, and the shortest path to reach that vertex using the view_path function.

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