Some notes regarding single source shortest path algorithms

Dijkstra and Bellman ford algorithms are popular algorithms for finding shortest distance between the nodes of a weighted graphs. Dijkstra algorithm has one limitation. It does not work well with a graph having negative weights. Bellman Ford algorithm works well with both positive and negative weights. In terms of cyclic graph, it works well with cyclic edges having total positive weight (e1 + e2 + e3…en> 0). Theoretically, shortest path for cyclic edges having negative total weight (e1 + e2 + e3….en) < 0 does not exist since during each cycle you can reduce total weight by some amount. Bellman Ford algorithm can identify such negative weight cycles in a graph.

Bellman Ford Algorithm:

The key idea is to find shortest distance

ith iteration -> Shortest distance having path length i

Since, acyclic graph has n vertices can have almost n — 1 edges, we iterate through n — 1 times to find the shortest path. During each iteration we relax the edges. Hence, total time complexity of entire algorithm would be (n — 1) * E = E * N or E * V if represent vertices as V instead of N. For cyclic graph with negative cycles, we don’t care cause shortest path does not exist for such graph. For cyclic graph with positive total weights, weights keep on increasing at every cycle iteration. We want to find shortest path, hence why would we care about iterating through again through cycles. So, we don’t care about cyclic total positive weight scenario as well.

Like Dijkstra, we create a distance array to keep track of shortest distance at each node which is common recurring part of shortest path algorithms.