Bellman-Ford's Algorithm

Description:

Bellman-Ford's Algorithm solves the problem of finding shortest paths from a source vertex v to all other vertices in the weighted graph. This algorithm supports negative weights as well.

Input:

A Connected and Weighted Graph G(E,V). Let's say nodes are numbered from 0 to N - 1.

Output:

The value of the Shortest path from node 0 to node N-1.

Implementation:

void bellman_ford(int n, int start) {
  dist[start] = 0;
  for (int i = 0; i < n - 1; i++) {
    for (int u = 0; u < n; u++) {
      for (int j = 0; j < adj[u].size(); j++) {
        int v = adj[u][j].v;
        int w = adj[u][j].weight;
        dist[v] = min(dist[v], w + dist[u]);
      }
    }
  }
}