Single Source Shortest Path Algorithms
Compare Bellman-Ford (handles negative weights) and Dijkstra (faster for positive weights)
Single Source Shortest Path Algorithms
Algorithms to find shortest paths from a single source vertex to all other vertices in a weighted graph.
Theory & Concepts
Definition:
Single source shortest path algorithms find the shortest paths from one source vertex to all other vertices in a weighted graph.
Key Points:
- Bellman-Ford: Handles negative edge weights, detects negative cycles, O(VE) complexity
- Dijkstra: Only positive weights, greedy approach, O(V²) or O((V+E)logV) complexity
- Both use relaxation technique to improve distance estimates
- Choice depends on graph properties (negative weights vs. performance)
Applications:
- GPS navigation and route planning
- Network routing protocols
- Currency arbitrage detection (Bellman-Ford)
- Social network analysis
University Guidelines
Exam Weightage
10-12 marks MarksSyllabus Coverage:
- Single source shortest path problem
- Bellman-Ford algorithm implementation
- Dijkstra's algorithm (greedy approach)
- Negative cycle detection
- Comparison of different approaches
Common Questions:
- Implement Bellman-Ford algorithm
- Compare Bellman-Ford vs Dijkstra
- Handle graphs with negative weights
- Detect negative cycles
Exam Tips:
Show relaxation steps clearly
Maintain distance and predecessor arrays
For Bellman-Ford: perform V-1 iterations
Check for negative cycles in final iteration
Algorithm Details
Bellman-Ford: O(VE), Dijkstra: O(V²) or O((V+E)logV)
Time Complexity
O(V) for distance and predecessor arrays
Space Complexity
Algorithm Steps:
- 1Initialize distances: source = 0, others = ∞
- 2Bellman-Ford: Relax all edges V-1 times
- 3Dijkstra: Use priority queue, relax neighbors of minimum vertex
- 4Update distances when shorter path found
- 5Bellman-Ford: Check for negative cycles
- 6Return final distances and paths
Draw Your Graph
Instructions:
- Click "Add Node" then click on canvas to add vertices
- Click "Add Edge", set weight (can be negative), then click two nodes
- Red edges indicate negative weights
- Select algorithm and source node, then run
Algorithm Results
🗺️
Draw a graph and run an algorithm to see the shortest paths
Algorithm Comparison
Bellman-Ford Algorithm
- ✅ Handles negative edge weights
- ✅ Detects negative cycles
- ✅ Works with directed graphs
- ⏱️ Time: O(VE) - slower
- 📦 Space: O(V)
- 🎯 Use when: Graph has negative weights
Dijkstra's Algorithm
- ❌ Requires non-negative weights
- ❌ Cannot detect negative cycles
- ✅ Works with directed/undirected graphs
- ⚡ Time: O(V²) or O((V+E)logV) - faster
- 📦 Space: O(V)
- 🎯 Use when: All weights are positive