Selman ALPDÜNDAR

Comparison of Dijkstra’s algorithm and Floyd–Warshall algorithm

Floyd-Warshall Algorithm

Stephen Warshall and Robert Floyd independently discovered Floyd’s algorithm in 1962.

The algorithm solves a type of problem call the all-pairs shortest-path problem. Actually, the Warshall version of the algorithm finds the transitive closure of a graph but it does not use weights when finding a path.  The Floyd algorithm is essentially the same as the Warshall algorithm except it adds weight to the distance calculation.

This algorithm works by estimating the shortest path between two vertices and further improving that estimate until it is optimum.  Consider a graph G, with Vertices V numbered 1 to n.  The algorithm first finds the shortest path from i to j, using only vertices 1 to k, where k<=n.  Next, using the previous result the algorithm finds the shortest path from i to j, using vertices 1 to k+1.  We continue using this method until k=n, at which time we have the shortest path between all vertices. This algorithm has a time complexity of O(n3), where n is the number of vertices in the graph.  This is noteworthy because we must test up to n2 edge combinations.

Dijkstra’s algorithm

Edsger Dijkstra discovered Dijkstra’s algorithm in 1959. his algorithm solves the single-source shortest-path problem by finding the shortest path between a given source vertex and all other vertices. This algorithm works by first finding the path with the lowest total weight between two vertices. j and k.  It then uses the fact that a node r, in the path from j to k implies a minimal path from j to r. In the end, we will have the shortest path from a given vertex to all other vertices in the graph.  Dijkstra’s algorithm belongs to a class of algorithms known as greedy algorithms.  A greedy algorithm makes the decision that seems the most promising at a given time and then never reconsiders that decision

The time complexity of Dijkstra’s algorithm is dependent upon the internal data structures used for implementing the queue and representing the graph.  When using an adjacency list to represent the graph and an unordered array to implement the queue the time complexity is O(n2), where n is the number of vertices in the graph.  However, using an adjacency list to represent the graph and a min-heap to represent the queue the time complexity can go as low as O(e*log n), where e is the number of edges.  It is possible to get an even lower time complexity by using more complicated and memory intensive internal data structures, but that is beyond the scope of this paper.

Different Between Dijkstra’s and Floyd-Warshall algorithm

In Dijkstra’s algorithm time complexity is quadratic but in Floyd-Warshall algorithm it is cubic. In addition, the result of Dijkstra’s is just a subset of Floyd-Warshall algorithm. Dijkstra’s algorithm returns the shortest path between for a given vertex and all others but Floyd-Warshall algorithm returns the shortest path between all vertices. Dijkstra’s algorithm time complexity is  for a given vertex, but if we try to find  the shortest path for all vertex with Dijkstra’s algorithm then it will be   which is  equal time complexity of Floyd-Warshall algorithm  . If we try to find all shortest path between all vertex with Dijkstra’s algorithm, we will have the same efficiency and result as using Floyd’s algorithm. In conclusion in Floyd-Warshall algorithm there can be negative weighted but in Dijkstra’s algorithm there can not be.

Conclusion

Both Floyd’s and Dijkstra’s algorithm may be used for finding the shortest path between vertices.  The biggest difference is that Floyd’s algorithm finds the shortest path between all vertices and Dijkstra’s algorithm finds the shortest path between a single vertex and all other vertices.  The space overhead for Dijkstra’s algorithm is considerably more than that for Floyd’s algorithm.  In addition, Floyd’s algorithm is much easier to implement.

Reference Book: Hein 1995

Reference Websites :

Floyd-Warshall algorithm

Dijkstra’s algorithm



2 comments

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.