-1
$\begingroup$

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

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

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.

$\endgroup$

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