There are many “kinds” of shortest paths.
| Algorithm | Constraint | Typical | Worst Case |
|---|---|---|---|
| Topological Sort | No directed cycles | \(N+M\) | \(N+M\) |
| Dijkstra | No negative weights | \(M\log N\) | \(M\log N\) |
| Bellman-Ford | No negative cycles | \(NM\) | \(N+M\) |
| Bellman-Ford (early termination) | No negative cycles | \(NM\) | \(NM\) |