Menu
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 
303
The Shortest Path Faster Algorithm (SPFA) is an improvement of the Bellman–Ford algorithm which computes single-source shortest paths in a weighted directed graph. The algorithm is believed to work well on random sparse graphs and is particularly suitable for graphs that contain negative-weight edges.
Dijkstra's algorithm solves the single-source shortest path problem with non-negative edge weight.
Dijkstra's algorithm is used for our fastest path algorithm because it can find the shortest path between vertices in the graph. The coordinates on the arena are considered as the vertices in the graph.
In addition, Best First Search is not optimal [not guaranteed to find the shortest path], and also A*, if you do not use an admissible heuristic function, while Dijkstra's algorithm is always optimal, since it does not relay on any heuristic.
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).
61
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
