In the below PDF we discuss about Bellman Ford Algorithm in detail in simple language, Hope this will help in better understanding.

🔔 Bellman–Ford Algorithm

📝 What is Bellman–Ford Algorithm?

Bellman–Ford Algorithm is a graph algorithm used to find the shortest path from a single source vertex to all other vertices in a weighted graph.

Single Source
Shortest Path
(Handles Negatives)

🎯 Key Idea

• ✔ Dynamic Programming based
• ✔ Repeatedly relax all edges
• ✔ Works with negative edge weights
• ✔ Detects negative weight cycles

⬇️

📌 Graph Requirements

• ✔ Directed or undirected graph
• ✔ Weighted graph
• ✔ Negative edges allowed
• ❌ No negative cycle reachable from source

⚙️ Working of Bellman–Ford Algorithm

• Step 1: Set distance of source = 0
• Step 2: Set distance of all other vertices = ∞
• Step 3: Relax all edges (V − 1) times
• Step 4: Check for negative cycles

Relax Edges Again & Again

🔄 Edge Relaxation

Relaxation checks whether a shorter path exists through an edge.

• If dist[u] + weight(u,v) < dist[v]
• Update dist[v]

📌 Why (V − 1) Times?

• Shortest path has at most (V − 1) edges
• Each iteration improves distances
• Extra iteration → cycle detection

⚠️ Negative Weight Cycle Detection

After (V − 1) relaxations:

• If any distance can still be reduced
• → Graph contains a negative weight cycle

Distance keeps decreasing → Cycle Exists

⏱ Time Complexity

• Edge relaxation → O(E)
• Total iterations → (V − 1)
• Overall → O(V × E)

💾 Space Complexity

• Distance array → O(V)
• No extra complex data structure

📘 Example Explanation

• Initialize distances
• Relax all edges repeatedly
• Gradually shortest paths appear
• Final check finds negative cycle (if any)

Distances converge step by step

💡 Applications of Bellman–Ford Algorithm

• 🌐 Network routing protocols (RIP)
• 📦 Logistics with penalties
• 💱 Currency exchange (arbitrage detection)
• 🧠 Graphs with negative costs

⚖️ Bellman–Ford vs Dijkstra

• Bellman–Ford → Handles negative weights
• Dijkstra → Cannot handle negative weights
• Bellman–Ford → Slower
• Dijkstra → Faster using heap
• Bellman–Ford → Detects negative cycles
• Dijkstra → Cannot detect cycles

❌ Limitations

• ❌ Slow for large graphs
• ❌ High time complexity
• ❌ Inefficient compared to Dijkstra

📝 Exam Tip:
Bellman–Ford Algorithm finds the shortest path from a single source even when negative edge weights are present. It also detects negative weight cycles. Time complexity is O(V × E).