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.
|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.