The best shortest path algorithm

Asked 4/12, 2009 at 13:6 Answered 19/11, 2023 at 15:10

What is the difference between the "Floyd-Warshall algorithm" and "Dijkstra's Algorithm", and which is the best for finding the shortest path in a graph?

I need to calculate the shortest path between all the pairs in a net and save the results to an array as follows:

**A     B     C     D      E**
A 0     10    15    5     20
B 10     0    5     5     10
C 15     5    0     10    15
D 5      5    10    0     15
E 20     10    15   15    0

Maryannamaryanne answered 4/12, 2009 at 13:6 Comment(4)

but the other one was closed, mostly because of the user's bad english, and one of the solutions named these exact two algorithms as alternatives. If we close this as dup, how will the author find out more about the previous question? Will we really all be nice enough to go over there and vote to reopen? – Priscian 4/12, 2009 at 13:15

hi sorry, but wanted to add an array example with respect to a picture but I did not do – Maryannamaryanne 4/12, 2009 at 13:17

thanks, SilentGhost for re-edit my question – Maryannamaryanne 4/12, 2009 at 13:20

Shouldn't DE in that graph be 15? – Chelsea 4/12, 2009 at 13:42

Dijkstra's algorithm finds the shortest path between a node and every other node in the graph. You'd run it once for every node. Weights must be non-negative, so if necessary you have to normalise the values in the graph first.

Floyd-Warshall calculates the shortest routes between all pairs of nodes in a single run! Cycle weights must be non-negative, and the graph must be directed (your diagram is not).

Johnson's algorithm is using Dijkstra's algorithm to find all pairs in a single pass, and is faster for sparse trees (see the link for analysis).

Priscian answered 4/12, 2009 at 13:22 Comment(3)

From the wikipedia link you cite for Dijkstra: "the algorithm finds the path with lowest cost between that vertex and every other vertex" (my emphasis). You thus don't need to run it for every pair of vertex but only for every vertex. – Alfredoalfresco 4/12, 2009 at 13:43

You can convert an undirected graph to a directed graph by replacing every edge uv with two edges (u,v) and (v,u) with the same weight. Then presumably Floyd-Warshall should work just fine? – Hodden 4/12, 2009 at 13:50

err .. floyd-warshall does not require it to have non-negative edges, from wikipedia "is a graph analysis algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles)" – Palaeolithic 10/1, 2013 at 13:30

Floyd Warshall find the paths between all pairs of vertices, but Dijkstra only finds the path from one vertex to all others.

Floyd Warshall is O(|V|³) and Dikstra is O(|E| + |V| log |V|) but you'll have to run it V times to find all pairs which gives a complexity of O(|E * V| + |V²| log |V|) I guess. This means it's possibly faster to use Dijsktra repeatedly than the FW algorithm, I would try both approaches and see which one is fastest in the actual case.

Alfredoalfresco answered 4/12, 2009 at 13:11 Comment(1)

Francis Haart's comment: "@Andreas Brinck, in a complete graph, E=(V^2-V)/2, and dijkstra's would be no faster." – Licentious 15/2, 2012 at 0:15

Dijkstra finds the shortest path from only one vertex, Floyd-Warshall finds it between all of them.

Barbarity answered 4/12, 2009 at 13:13 Comment(0)

Use the Floyd-Warshall algorithm if you want to find the shortest path between all pairs of vertexes, as it has a (far) higher running time than Dijkstra's algorithm.

The Floyd-Warshall algorithm has a worst case performance of O(|V|³), where as Dijkstra's has a worse case performance of O(|E| + |V|log |V|)

Casa answered 4/12, 2009 at 13:11 Comment(0)

In the meanwhile better algorithms for the single source shortest path problem are known. A practically relevant one is a derivation of Dijkstra's algorithm by Torben Hagerup. The algorithm has the same worst case complexity as Djikstra's, but in the average case the expected runtime is linear in the size of the graph, which is much faster than the pure Dijkstra. The idea of the algorithm is based on the idea, that there is no need to always poll the minimum edge from the queue. It is possible poll an edge from the queue, whose weight is 1+k times as large as the minimum edge weight, where k is some number larger 0. Even if such an edge is chosen, the algorithm will still find the shortest path.

Angeli answered 17/10, 2012 at 5:34 Comment(1)

archived version: web.archive.org/web/20180613142303/https://link.springer.com/… – Otilia 23/12, 2019 at 17:15

Dijkstra's is mainly for single pair shortest path finding i.e. from one node to all other nodes, where as Floyd-Warshall is for all-pair shortest path i.e. shortest path between all pair of vertices. The Floyd-Warshall algorithm has a worst case performance of O(|V|3), where as Dijkstra's has a worse case performance of O(|E| + |V|log |V|) Also Dijkstra's cannot be used for negative weights ( we use Bellmann Ford for the same ). but for Floyd-Warshall we can use negative weights but no negative cycles

Harwell answered 11/7, 2012 at 8:9 Comment(0)

We can't directly compare "Floyd-Warshall" and "Dijkstra" algorithms as both serve a little different purpose. Please refer the table below to make the best choice.

Algorithm	Time Complexity (Big O)	Space Complexity (Big O)	Direct or undirect graph?	Handle cyclic graph?	Handle negative edge weight?	When to use?
Dijkstra's Algorithm	(E+V)LogV	V	Both	No	No	Get shortest paths from single source to all vertices
Bellman-Ford Algorithm	VE	V	Both	Doesn't work for negative weight cycle	yes	Get shortest paths from single source to all vertices
Topological sort Algorithm	V+E	V	Direct	No	Yes	Get shortest paths from single source to all vertices
Floyd-Warshall algorithm	V^3	V^2	Both	Doesn't work for negative weight cycle	Yes	Get shortest paths from all vertices to all vertices

Astrology answered 19/11, 2023 at 15:10 Comment(1)

Please don't post the same answer at multiple questions – Clarhe 19/11, 2023 at 17:4

Recommended topics

Hot tags