Bellman-ford algorithm

Write a program to implement the Bellman-ford algorithm

Example 1:

Input: n=6,edges={{1,2,10},{2,1,10},{2,3,5},{3,2,5},{1,3,35},{3,1,35},{1,6,50},{6,1,50},{6,2,50},{4,3,25},{5,3,5},{5,4,6},{2,6,10},{3,4,25},{3,5,5},{4,5,6}},source=1
Output: 0 10 15 26 20 20

Approach:

Java

import java.util.ArrayList;

public class BellmanFordAlgorithm {
    public static void main(String[] args) {
        int n = 6;
        // all edges in the graph
        // graph is undirected
        ArrayList<Edge> edges = new ArrayList<>();
        addEdge(edges, 1, 2, 10);
        addEdge(edges, 2, 1, 10);
        addEdge(edges, 2, 3, 5);
        addEdge(edges, 3, 2, 5);
        addEdge(edges, 1, 3, 35);
        addEdge(edges, 3, 1, 35);
        addEdge(edges, 1, 6, 50);
        addEdge(edges, 6, 1, 50);
        addEdge(edges, 6, 2, 10);
        addEdge(edges, 4, 3, 25);
        addEdge(edges, 5, 3, 5);
        addEdge(edges, 5, 4, 6);
        addEdge(edges, 2, 6, 10);
        addEdge(edges, 3, 4, 25);
        addEdge(edges, 3, 5, 5);
        addEdge(edges, 4, 5, 6);

        // source vertex
        int source = 1;

        int distance[] = bellmanFord(edges, n,
                     edges.size(), source);
        // iterate from start edge to max edge
        System.out.print("Distance is ");
        for (int i = 1; i < distance.length; i++) {
            System.out.print(distance[i] + " ");
        }

    }

    private static int[] bellmanFord(ArrayList<Edge> edges, 
                int n, int m, int source) {

        // vector to store the distance
        // of all nodes initialize with INT_MAX(infinite)
        int distance[] = new int[n + 1];
        for (int i = 1; i < distance.length; i++) {
            distance[i] = Integer.MAX_VALUE;
        }
        distance[source] = 0;

        // vector to store the parent
        // of all nodes initialize with -1
        int parent[] = new int[n + 1];
        for (int i = 1; i < parent.length; i++) {
            parent[i] = Integer.MAX_VALUE;
        }
        parent[source] = -1;
        boolean flag = false;
        for (int i = 0; i < n; i++) {
            flag = false;
            for (int j = 0; j < m; j++) {
                if (distance[edges.get(j).a] 
                        < Integer.MAX_VALUE) {
                    // if previous distance is more
                    // then update with new distance
                    if (distance[edges.get(j).b] >
                                distance[edges.get(j).a] + edges.get(j).w) {
                        flag = true;
                        // update the distance
                        distance[edges.get(j).b] = 
                        distance[edges.get(j).a] + edges.get(j).w;

                        // make parent as current node
                        parent[edges.get(j).b] = edges.get(j).a;
                    }
                }
            }
            // if their is no update we
            // break out of loop because in
            // further steps their is also no update
            if (flag == false)
                break;
        }

        return distance;
    }

    // method for add edges into adj
    private static void addEdge(ArrayList<Edge> edges,
                 int a, int b, int w) {
        edges.add(new Edge(a, b, w));
    }
}

// Edge classes
class Edge {
    int a;
    int b;
    int w;

    public Edge(int a, int b, int w) {
        super();
        this.a = a;
        this.b = b;
        this.w = w;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;
#define INF 100000000
//structure for the Edges of
//the graph
struct Edge
{
    int a;
    int b;
    int w;
};

//Edge to store the edges 
//of the graph
Edge arr[1000001];
vector<int> bellmanFord(int n,int m,int source)
{
   //vector to store the distance of
   //all nodes initialize with INF
   vector<int> dist(n+1,INF);

   //vector to store the parent
   //of all nodes initialize with -1
   vector<int> parent(n+1,-1);
   
   //make diatance of source as 0
   dist[source]=0;

   //make parent of source as null
   parent[source]=-1;


   bool flag;

   //iterate for all the nodes
   for(int i=0;i<n-1;i++)
     {
         flag=false;

         //iterate  for all the edges
         for(int j=0;j<m;j++)
            {
                if(dist[arr[j].a]<INF)
                  {
                      //if previous distance is more
                      //then update with new distance
                      if(dist[arr[j].b]>dist[arr[j].a]+arr[j].w)
                         {
                             flag=true;
                            //update the distance
                             dist[arr[j].b]=dist[arr[j].a]+arr[j].w;

                             //make parent as current node
                             parent[arr[j].b]=arr[j].a;
                         }
                  }
            }
        //if their is no update we 
        //break out of loop because in 
        //furthur steps their is also no update
          if(flag==false)
             break;
     }
   return dist;
}
int main()
{
     int n=6;
     //all edges in the graph 
     //graph is undirected
     vector<vector<int>> edges={{1,2,10},{2,1,10},{2,3,5},
                             {3,2,5},{1,3,35},{3,1,35},
                             {1,6,50},{6,1,50},{6,2,10},
                             {4,3,25},{5,3,5},{5,4,6},
                             {2,6,10},{3,4,25},{3,5,5},
                             {4,5,6}};

   //insert all edges into the list
    for(int i=0;i<edges.size();i++)
      {
          arr[i].a=edges[i][0];
          arr[i].b=edges[i][1];
          arr[i].w=edges[i][2];
      }
  //source vertex
  int source=1;

   vector<int> dist=bellmanFord(n,edges.size(),source);

   //print the distance of all nodes

   for(int i=1;i<=n;i++)
     {
         if(dist[i]==INF)
            cout<<"inf ";
         else
           cout<<dist[i]<<" ";
     }
   return 0;
}