codaBack to Academy
graphs
Bellman-Ford
Bellman-Ford computes shortest paths from a single source vertex to all other vertices, even when edge weights are negative. It relaxes all edges V-1 times and can detect negative-weight cycles. It is preferred over Dijkstra's when the graph may contain negative edge weights.
Use Cases
- •Graphs with negative edge weights
- •Detecting negative-weight cycles in financial arbitrage
- •Distance-vector routing protocols (RIP)
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O(V * E) | O(V * E) | O(V * E) |
| Space | O(V) | ||
Visualization
Implementation
Output
Click "Run Code" to see output...