I do not understand the difference between the All Pairs Shortest Path problem (solved by the Floyd–Warshall algorithm) and the Shortest Path problem (solved by Dijkstra's algorithm).


closed as unclear what you're asking by hengxin, David Richerby, Evil, Rick Decker, Juho Dec 22 '16 at 8:30

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ Have you read any resource on this? Even Wikipedia explains this reasonable well. $\endgroup$ – Raphael Dec 16 '16 at 6:10

All-pairs shortest paths using Floyd-Warshall leads to determination of a value for all pairs of nodes that describes shortest distance of any path that exists between those two nodes. Note that sometimes, two nodes will have no path between them. Also, the graph that we apply the algorithm to may be directed, so one node may have a distance to a second node, but the reverse is not true. It classically takes $O(|V| ^ 3)$ time.

Dijkstra's algorithm solves the single-source shortest paths problem. It classically takes $O(|E| + |V| \cdot \log(|V|))$ time. Note that for dense graphs, $|E|$ = $O(|V| ^ 2)$, so we could say that Dijkstra's is $O(|V|)$ times faster than Floyd-Warshall.


Not the answer you're looking for? Browse other questions tagged or ask your own question.