Introduction
Prerequisites: Graph Theory
The shortest path is defined as a path from one node to another while trying to minimize a certain property (least number of nodes, smallest total weight). However, shortest paths may have negative weights which leads to cycles.
Implementations
| Algorithm | Time | Detect cycles? |
|---|---|---|
| Floyd Warshall | O(N3) | Yes |
| Bellman Ford | O(N2) | Yes |
| Dijkstra's | O(N log N) | No |
- Floyd Warshall computes the shortest path between all pairs of nodes.
- Bellman Ford computes the shortest path between one node to every other node.
- Dijkstra's computes the shortest path between two nodes.