Bellman-Ford Algorithm (Dynamic Programming)
Find shortest paths from a source vertex with negative edge weights and detect negative cycles
Bellman-Ford Single Source Shortest Path Algorithm
The Bellman-Ford algorithm finds shortest paths from a source vertex to all other vertices in a weighted directed graph. It can handle negative edge weights and detect negative cycles.
Theory & Concepts
Definition:
A dynamic programming algorithm that computes shortest paths from a single source vertex to all other vertices in a weighted directed graph, even with negative edge weights.
Key Points:
- Can handle negative edge weights (unlike Dijkstra)
- Detects negative weight cycles
- Uses dynamic programming approach with relaxation
- Runs in O(VE) time complexity
Applications:
- Network routing with cost considerations
- Currency arbitrage detection
- Game theory and economics
- Distance vector routing protocols
University Guidelines
Exam Weightage
8-10 marks MarksSyllabus Coverage:
- Bellman-Ford algorithm implementation
- Negative cycle detection
- Single source shortest path problem
- Dynamic programming approach
- Comparison with Dijkstra's algorithm
Common Questions:
- Implement Bellman-Ford algorithm
- Detect negative cycles in graph
- Find shortest paths with negative edges
- Compare with Dijkstra's algorithm
Exam Tips:
Show V-1 iterations of edge relaxation
Check for negative cycles in Vth iteration
Maintain distance and predecessor arrays
Show step-by-step relaxation process
Algorithm Details
O(VE) where V is vertices and E is edges
Time Complexity
O(V) for distance and predecessor arrays
Space Complexity
Algorithm Steps:
- 1Initialize distances: source = 0, others = ∞
- 2Repeat V-1 times: relax all edges
- 3For each edge (u,v): if dist[u] + weight < dist[v], update dist[v]
- 4Check for negative cycles: run one more iteration
- 5If any distance can be reduced, negative cycle exists
- 6Return shortest distances and cycle detection result
Draw Your Graph
Instructions:
- Click "Add Node" then click on canvas to add vertices
- Add Edge: Click "Add Edge", set weight, then click two nodes to connect them
- Negative weights are allowed and shown in red
- Drag nodes to move them around (not available in edge mode)
- Click "Delete" then click nodes to remove them (can be undone)
- Use Undo/Redo to restore accidentally deleted items
- Select source node and run the algorithm to find shortest paths
- Red source node shows where shortest path calculation starts
Algorithm Results
🔄
Draw a graph and click "Run Bellman-Ford Algorithm" to find shortest paths