Bellman-Ford Algorithm - Shortest Path Algorithm

"The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph.For graphs with only non-negative edge weights, the faster Dijkstra's algorithm also solves the problem. Thus, Bellman–Ford is used primarily for graphs with negative edge weights. The algorithm is named after its developers, Richard Bellman and Lester Ford, Jr. 

Negative edge weights are found in various applications of graphs, hence the usefulness of this algorithm. However, if a graph contains a "negative cycle", i.e., a cycle whose edges sum to a negative value, then walks of arbitrarily low weight can be constructed by repeatedly following the cycle, so there may not be a shortest path. In such a case, the Bellman-Ford algorithm can detect negative cycles and report their existence, but it cannot produce a correct "shortest path" answer if a negative cycle is reachable from the source." - Wikipedia

INITIALISE_SINGLE_SOURCE(G, start)
{
  for each vertex v ∈ v(G)
    dist[v] <- ∞
    pred[v] <- NIL
  dist[start] <- 0
}
// dist[v] <- distance of vertex "v" from vertex "start"
// pred[v] <- predecessor of "v" in the shortest path 
//            from "start"

RELAX(u, v, cost)
{
  if dist[v] > dist[u] + cost[u, v]
    dist[v] <- dist[u] + cost[u, v]
    pred[v] <- u
} 

BELLMAN_FORD(G, cost, start)
{
  INITIALISE_SINGLE_SOURCE(G, start)
  for i <- 1 to |v(G)| - 1
    do for each edge (u, v) ∈ E[G]
      do RELAX(u, v, cost)
  for each edge (u, v) ∈ E[G]
    do if dist[v] > dist[u] + cost[u, v]
      then return FALSE
  return TRUE
}

Written by Munia Balayil
Image courtesy - ArsRout