CODEWITHSUNDEEP
algorithmshortest-path
Ricardo Rod
Ricardo Rod

Reputation: 8911

The best shortest path algorithm

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

Upvotes: 28

Views: 44558

Answers (7)

Vipul Kumar
Vipul Kumar

Reputation: 661

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

Upvotes: 0

SpaceTrucker
SpaceTrucker

Reputation: 13556

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.

Upvotes: 1

Will
Will

Reputation: 75625

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

Upvotes: 25

piyush_raman
piyush_raman

Reputation: 318

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

Upvotes: 0

Andreas Brinck
Andreas Brinck

Reputation: 52519

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|3) 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| + |V2| 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.

Upvotes: 8

Gergely Orosz
Gergely Orosz

Reputation: 6485

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

Upvotes: 5

Yacoby
Yacoby

Reputation: 55445

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|3), where as Dijkstra's has a worse case performance of O(|E| + |V|log |V|)

Upvotes: 4

Related Questions