Shortest path algorithms

Post date: Oct 19, 2016 5:14:9 PM

Q: What are the main shortest path algorithms?

A:

• • Dijkstra's algorithm: single-source shortest path, nonnegative weights.

  • Bellman-Ford algorithm: single-source shortest path, negative weights.O(VE)

  • Floyd-Warshall's algorithm: all-pairs shortest path. O(V^3)

For more details, see [1] and, especially, [2].

[1] http://cs.stackexchange.com/questions/2942/am-i-right-about-the-differences-between-floyd-warshall-dijkstra-and-bellman-fo

[2] https://github.com/long0612/randProbs