Bellman-Ford Algorithm Lecture Notes

Introduction

• The Bellman-Ford algorithm is used for finding the shortest path in a graph.
• It differs from Dijkstra's algorithm, particularly in its handling of graphs with negative edges and cycles.

Key Differences from Dijkstra's Algorithm

• Negative Edges:
  • Dijkstra's algorithm fails with graphs containing negative edges.
  • Bellman-Ford can handle negative edges and check for negative cycles.
• Negative Cycles:
  • Dijkstra's does not detect negative cycles; it runs indefinitely.
  • Bellman-Ford detects negative cycles effectively.

Applicability

• Bellman-Ford algorithm is applicable only to Directed Graphs (DG).
• For undirected graphs, convert them to directed by creating two directed edges for each undirected edge with the same weight.

Understanding Negative Cycles

• A negative cycle exists if there is a path with a total weight less than zero.
• Example: A cycle with edge weights of -2, -1, and +2 results in a total weight of -1, indicating a negative cycle.

Implementation Overview

1. Initialization:
   • Create a distance array initialized to infinity, except the source node which is set to 0.
2. Relaxation Process:
   • Relax all edges (n-1) times, where n is the number of nodes.
   • Relaxation: Check if the distance to the destination node can be improved.
3. Relaxation Definition:
   • If distance[u] + weight < distance[v], update distance[v].
4. Iteration Explanation:
   • Perform this relaxation process n-1 times to ensure that all shortest paths are found.

Why n-1 Relaxations?

• Each node can potentially be reached through another node, requiring n-1 iterations for all nodes to be updated correctly.
• Example with 4 edges confirms that the last node can update paths after n-1 iterations.

Detecting Negative Cycles

• After n-1 iterations, perform one more relaxation. If any distance can still be updated, a negative cycle exists.

Coding Example

• Pseudocode:
  • Initialize distance array with infinity.
  • Relax edges for (n-1) iterations.
  • Check for negative cycles after (n-1) iterations.

Complexity

• Time Complexity: O(V * E)
• Space Complexity: O(V)
• Bellman-Ford is more time-consuming than Dijkstra's (which is O(E log V)), but it's essential for graphs with negative weights.*

Conclusion

• Bellman-Ford is crucial when dealing with negative edge weights or negative cycles.
• Generally, algorithms like Dijkstra's are preferred unless negative edges are present.

Call to Action

• Like the video and subscribe to the channel for more content!
• Check out related series linked in the description.