Bellman Ford Algorithm | Distance from the Source Explained Step-by-Step

Bellman Ford Algorithm made easy: learn how to find shortest paths (and detect negatives) with clear intuition, commented Python code, dry run, and Big-O.

Here’s the [Problem Link] to begin with.

1. What does the problem ask?

Given:

• V vertices (0 … V-1)
• a list of directed edges [u, v, w] (w may be negative)
• a source vertex src

Return an array dist where dist[i] is the shortest distance from src to i.
If the graph has a negative-weight cycle reachable from src, return [-1].

2. Mini example

V = 5
edges = [
  [0,1,6], [0,2,7], [1,2,8], [1,3,5],
  [1,4,-4], [2,3,-3], [2,4,9], [3,1,-2],
  [4,3,7],  [4,0,2]
]
src = 0

Shortest distances = [0, 2, 7, 4, -2]
(No negative cycle exists.)

3. Why use the Bellman Ford Algorithm?

• Handles negative weights safely.
• Detects negative cycles.
• Works in O(V × E) time – slower than Dijkstra but more general.

Idea:

1. Relax every edge V – 1 times.
   After these rounds, all shortest paths (which have at most V-1 edges) are fixed.
2. One more scan – if any edge can still relax, a negative cycle is reachable.

4. Python code

class Solution:
    def bellmanFord(self, V, edges, src):
        INF = 10**8                       # a very large number
        dist = [INF for _ in range(V)]
        dist[src] = 0                     # distance to source is zero

        # repeat edge relaxation V-1 times
        for _ in range(V - 1):
            for u, v, w in edges:
                if dist[u] != INF and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

        # check for negative-weight cycles
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                return [-1]               # cycle found

        return dist                       # shortest distances

5. Step-by-step explanation

1. dist array – start with “infinity” except the source.
2. Main loop (V-1 rounds)
   • For every edge, try to go “one step further”.
   • If going through u shortens v, store the better value.
3. Cycle test
   • After V-1 rounds, shortest paths are done.
   • A further improvement means distance can shrink forever → negative cycle.
4. Return
   • [-1] if a cycle exists; otherwise the dist list.

6. Dry run (tiny graph)

Edges
0→1 (4), 0→2 (5), 1→2 (-2)

Final distances: 0, 4, 2.

7. Complexity

8. Conclusion

• The Bellman Ford Algorithm is the go-to tool when edges may be negative.
• Relax each edge for V-1 rounds, then do one extra check for cycles.
• Simple loops, no fancy data structures – perfect for interviews dealing with tricky weights.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.