Bellman-Ford Algorithm: Finding shortest path from a node

#include <stdio.h>
void relax(int u, int v, double w, double d[], int pi[]) {
  if (d[v] > d[u] + w) {
    d[v] = d[u] + w;
    pi[v] = u;
  }
}
void initialize_single_source(double d[], int pi[], int s, int n) {
  int i;
  for (i = 1; i<= n; ++i) {
    d[i] = 1000000000.0;
    pi[i] = 0;
  }
  d[s] = 0.0;
}
int bellman_ford(int first[], int node[], int next[], double w[], double d[],
  int pi[], int s, int n) {
  int u, v, i, j;
  initialize_single_source(d, pi, s, n);
  for (i = 1; i<= n-1; ++i) {
    for (u = 1; u <= n; ++u) {
      j = first[u];
      while (j > 0) {
       v = node[j];
       relax(u, v, w[j], d, pi);
       j = next[j];
     }
   }
 }
 for (u = 1; u <= n; ++u) {
  j = first[u];
  while (j > 0) {
    v = node[j];
    if (d[v] > d[u] + w[j])
     return 0;
   j = next[j];
 }
}
return 1;
}
int main(void) {
  int first[6], node[11], next[11], pi[6];
  double w[11], d[6];
  int s;
  int i;
  int ok;
  first[1] = 1;
  first[2] = 3;
  first[3] = 6;
  first[4] = 7;
  first[5] = 9;
  node[1] = 2;
  node[2] = 4;
  node[3] = 3;
  node[4] = 4;
  node[5] = 5;
  node[6] = 2;
  node[7] = 3;
  node[8] = 5;
  node[9] = 1;
  node[10] = 3;
  w[1] = 6.0;
  w[2] = 7.0;
  w[3] = 5.0;
  w[4] = 8.0;
  w[5] = -4.0;
  w[6] = -2.0;
  w[7] = -3.0;
  w[8] = 9.0;
  w[9] = 2.0;
  w[10] = 7.0;
  next[1] = 2;
  next[2] = 0;
  next[3] = 4;
  next[4] = 5;
  next[5] = 0;
  next[6] = 0;
  next[7] = 8;
  next[8] = 0;
  next[9] = 10;
  next[10] = 0;
  printf("Enter source node: ");
  scanf("%d", &s);
  ok = bellman_ford(first, node, next, w, d, pi, s, 5);
  printf("bellman_ford returns ");
  printf("%d\n\n", ok);
  for (i = 1; i<= 5; ++i) {
    printf("%d: %f  %d\n", i, d[i], pi[i]);
  }
  return 0;
}

#include <iostream>
#include <map>
#include <vector>
#include <utility>
#include <unordered_map>
#include <algorithm>
#include <string>
#include <climits>
int nodes,edges;
// Path of Cosmos by OpenGenus Foundation
void path_finding(int source, std::unordered_map<int,int> parent_map)
{
	using namespace std;
	string str;
	while(parent_map[source]!=source)
	{
		str.append(to_string(source));
		str.append(" ");
		source=parent_map[source];
	}
	str.append(to_string(source));
	reverse(str.begin(),str.end());
	cout<<"Path\n";
	cout<<str<<endl;
}
void print_distance(std::vector<int> distance)
{
	using namespace std;
	cout << "Distance of vertex corresponding from source\n";
	for(size_t i=0; i < distance.size(); ++i)
	{
		cout << i << "\t\t" << distance[i] << endl;
	}
}
void BellmanFord(std::vector<std::pair<int, std::pair<int,int>> > graph, int source, std::unordered_map<int,int> &parent_map)
{
	using namespace std;
	vector<int> distance(nodes, INT_MAX);
	distance[source]=0;
// Relax all edges nodes-1 times to get the shortest possible distance
	for(int i=0;i<nodes;i++)
	{
		for(int j=0;j<edges;j++)
		{
			int source=graph[j].second.first;
			int destination=graph[j].second.second;
			int weight=graph[j].first;
			if(distance[source]!=INT_MAX&&distance[source]+weight<distance[destination])
			{
				distance[destination]=distance[source]+weight;
				parent_map[destination]=source;
			}
		}
	}
/* If after relaxing all edges for nodes-1 time we still get a shorter path that indicates
 a negative weight cycle */
	for(int j=0;j<edges;j++)
		{
			int source=graph[j].second.first;
			int destination=graph[j].second.second;
			int weight=graph[j].first;
			if(distance[source]!=INT_MAX&&distance[source]+weight<distance[destination])
			{
				cout<<"Graph contains negative weight cycle\n";
				exit(0);
			}
		}
	print_distance(distance);
}
int main()
{
	using namespace std;
	vector<pair<int,pair<int,int>> > graph;
	unordered_map<int,int> parent_map;
	int source,init_path;
	cout<<"Enter number of nodes in graph\n";
	cin>>nodes;
	cout<<"Enter number of edges is graph\n";
	cin>>edges;
	for(int i=0;i<edges;i++)
	{
		int src,dest,weight;
		cout<<"Enter source vertex(zero indexed)\n";
		cin>>src;
		cout<<"Enter destination vertex(zero indexed)\n";
		cin>>dest;
		cout<<"Enter weight of edge\n";
		cin>>weight;
		graph.push_back(make_pair(weight,make_pair(src,dest)));
	}
	cout<<"Enter initial vertex(zero indexed)\n";
	cin>>source;
	BellmanFord(graph,source,parent_map);
	cout<<"Enter destination vertex for path finding(zero indexed)\n";
	cin>>init_path;
	path_finding(init_path,parent_map);
	return 0;
}

/**
 * An implementation of the Bellman-Ford algorithm. The algorithm finds
 * the shortest path between a starting node and all other nodes in the graph. 
 * The algorithm also detects negative cycles.
 *
 * @author William Fiset, william.alexandre.fiset@gmail.com
 **/
public class BellmanFordEdgeList {
  // A directed edge
  public static class Edge {
    double cost;
    int from, to;
    public Edge(int from, int to, double cost) {
      this.to = to;
      this.from = from;
      this.cost = cost;
    }
  }
  /**
   * An implementation of the Bellman-Ford algorithm. The algorithm finds
   * the shortest path between a starting node and all other nodes in the graph. 
   * The algorithm also detects negative cycles. If a node is part of a negative 
   * cycle then the minimum cost for that node is set to Double.NEGATIVE_INFINITY.
   *
   * @param edges - An edge list containing directed edges forming the graph
   * @param V     - The number of vertices in the graph.
   * @param start - The id of the starting node
   **/
  public static double[] bellmanFord(Edge[] edges, int V, int start) {
    double[] dist = new double[V];
    java.util.Arrays.fill(dist, Double.POSITIVE_INFINITY);
    dist[start] = 0;
    // For each vertex, apply relaxation for all the edges
    for (int v = 0; v < V-1; v++)
      for (Edge edge : edges)
        if (dist[edge.from] + edge.cost < dist[edge.to])
          dist[edge.to] = dist[edge.from] + edge.cost;
    // Run algorithm a second time to detect which nodes are part
    // of a negative cycle. A negative cycle has occurred if we 
    // can find a better path beyond the optimal solution.
    for (int v = 0; v < V-1; v++)
      for (Edge edge : edges)
        if (dist[edge.from] + edge.cost < dist[edge.to])
          dist[edge.to] = Double.NEGATIVE_INFINITY;
    // Return the array containing the shortest distance to every node
    return dist;
  }
  public static void main(String[] args) { 
    int E = 10, V = 9, start = 0;
    Edge [] edges = new Edge[E];
    edges[0] = new Edge(0,1,1);
    edges[1] = new Edge(1,2,1);
    edges[2] = new Edge(2,4,1);
    edges[3] = new Edge(4,3,-3);
    edges[4] = new Edge(3,2,1);
    edges[5] = new Edge(1,5,4);
    edges[6] = new Edge(1,6,4);
    edges[7] = new Edge(5,6,5);
    edges[8] = new Edge(6,7,4);
    edges[9] = new Edge(5,7,3);
    double[] d = bellmanFord(edges, V, start);
    for (int i = 0; i < V; i++)
      System.out.printf("The cost to get from node %d to %d is %.2f\n", start, i, d[i] );
    // Output:
    // The cost to get from node 0 to 0 is 0.00
    // The cost to get from node 0 to 1 is 1.00
    // The cost to get from node 0 to 2 is -Infinity
    // The cost to get from node 0 to 3 is -Infinity
    // The cost to get from node 0 to 4 is -Infinity
    // The cost to get from node 0 to 5 is 5.00
    // The cost to get from node 0 to 6 is 5.00
    // The cost to get from node 0 to 7 is 8.00
    // The cost to get from node 0 to 8 is Infinity
  }
}

# part of cosmos by OpenGenus Foundation
from collections import defaultdict
# Part of Cosmos by OpenGenus Foundation
class Graph:
	def __init__(self,vertices):
		self.V = vertices # # of vertices
		self.graph = []
	# add edge to graph
	def addEdge(self, u,v,w):
		self.graph.append([u,v,w])
	# print solution
	def printArr(self,dist):
		print("Vertex Distance from Source ")
		for i in range(self.V):
			print("%d -> %d" % (i,dist[i]))
	# main function for bellman ford algo. Also detects negative weight cycles
	def bellmanFord(self,src):
		# init all distances from source to all as INFINITE
		dist = [float("Inf")] * self.V
		dist[src] = 0
		# relax all edges |V|-1 times.
		for i in range(self.V - 1):
			# update dist value and parent index of adjacent values of picked vertex.
			# consider those which are still in queue.
			for u, v, w in self.graph:
				if dist[u] != float("Inf") and dist[u] + w < dist[v]:
					dist[v] = dist[u] + w
		# check for negative weight cycles. If path obtained from above step (shortest distances)
		# is shorter, there's a cycle. So quit.
		for u, v, w in self.graph:
		 	if dist[u] != float("Inf") and dist[u] + w < dist[v]:
		 		print("Negative Cycles !")
		 		return
		# print distances
		self.printArr(dist)
# dry run
if __name__ == "__main__":
	g = Graph(5)
	g.addEdge(0, 1, -1)
	g.addEdge(0, 2, 4)
	g.addEdge(1, 2, 3)
	g.addEdge(1, 3, 2)
	g.addEdge(1, 4, 2)
	g.addEdge(3, 2, 5)
	g.addEdge(3, 1, 1)
	g.addEdge(4, 3, -3)
	g.bellmanFord(0)

<?php 
/*Part of Cosmos by OpenGenus Foundation*/
/*{source, destination, distance}*/
$edges =    array(
           array(0,1,5),
           array(0,2,8),
           array(0,3,-4),
           array(1,0,-2),
           array(2,1,-3),
           array(2,3,9),
           array(3,1,7),
           array(3,4,2),
           array(4,0,6),
           array(4,2,7),
       );
BellmanFord($edges,10,5,4);
function BellmanFord($edges, $edgecount, $nodecount, $source) { 
    // Initialize distances
    $distances = array();
    // This is the initialize single source function.
    for($i =0; $i < $nodecount; ++$i)
      $distances[$i]= INF;
      $distances[$source]=0;
     // Do what we are suppose to do, This is the BellmanFord function
     for($i =0; $i < $nodecount;++$i) {
         $somethingChanged =false;
         for($j =0; $j < $edgecount;++$j) {
             if($distances[$edges[$j][0]]!= INF) { 
                 $newDist = $distances[$edges[$j][0]]+ $edges[$j][2];
                if($newDist < $distances[$edges[$j][1]]) { 
                     $distances[$edges[$j][1]]= $newDist;
                     $somethingChanged =true;
                }
            }
        }
       // If $somethingChanged == FALSE, then nothing has changed and we can go on with the next step.
       if(!$somethingChanged)break;
    }
   // Check the graph for negative weight cycles
   for($i =0; $i < $edgecount;++$i) {
        if($distances[$edges[$i][1]] > $distances[$edges[$i][0]]+ $edges[$i][2]){
            echo "Negative edge weight cycle detected!";
            return;
        }
    }
   // Print out the shortest distance
    for($i =0; $i < $nodecount;++$i) {
        echo "Shortest distance between nodes ". $source . " and ". $i ." is ". $distances[$i];
        echo "<br>";
    }
   return;
}
?>