1. Introduction
In this tutorial, we’ll discuss the key differences between the Dijkstra and Floyd-Warshall shortest path algorithms. Further, we’ll compare them based on various properties for deeper understanding.
Both algorithms apply to a class of data structures known as graphs. A graph is characterized by a set of nodes or vertices labeled 
, and the set of connections or edges between these nodes labeled 
. Additionally, we assign a non-negative integer weight to each edge which represents the distance metric between a pair of nodes. A path between two nodes has a distance that is the sum of the weights of its constituent edges. With this in mind, the key idea is to find the path with the minimum distance between pairs of nodes:
In the above example, 
and 
. Weights are shown above the edges.
Correspondingly, we’ll recall the specific problems that these algorithms solve.
2. Dijkstra’s Algorithm
It solves the Single Source Shortest Path (SSSP) problem. That is, we wish to find the shortest path from a single source node to a given destination node. A pertinent application of this algorithm is in the link-state routing protocol, where each node uses it to create an internal picture of the network.
3. Floyd-Warshall Algorithm
It solves the All-Pairs Shortest Paths (APSP) problem. In particular, we find the shortest paths between all pairs of nodes in the graph, which is computationally more expensive. This computational expense manifests in both the space required to store graph data and the time required to process it. Nevertheless, the Floyd-Warshall algorithm remains useful due to its simplicity of implementation.
4. Comparison
In this section, we’ll do a side-by-side comparison based on the properties of each algorithm.
4.1. Algorithmic Paradigm
Dijkstra’s algorithm follows the greedy paradigm. In other words, it makes locally optimal choices at each step leading to a globally optimal solution on termination. The defining characteristics of a problem which a greedy algorithm can solve are optimal substructure and the greedy choice property. Such algorithms execute in a top-down fashion.
By optimal substructure, we mean that an optimal solution to a problem consists of optimal solutions to its subproblems. For example, the SSSP problem possesses optimal substructure but the Unweighted Longest Simple Path problem does not.
The greedy choice property states that if the algorithm makes a greedy choice at the first step, then there exists an optimal solution that is compatible with it. In particular, making a greedy choice restricts the subproblems that we have to solve.
In contrast, Floyd-Warshall’s algorithm follows the dynamic programming (DP) paradigm. Such algorithms either execute top-down with memoization applied or construct solutions bottom-up. Problems solvable by DP possess optimal substructure and overlapping subproblems.
A problem is said to have overlapping subproblems if the same subproblems are solved at multiple steps of the algorithm. Thus, its subproblem space is small enough that no new subproblems are generated.
4.2. Asymptotic Analysis
All in all, there are three ways to implement Dijkstra’s algorithm.
- arrays: insert and decrease key operations cost
while min-extraction costs 
, leading to 
overall. - min-heaps: decrease key and min-extraction operations cost
and are done 
and times respectively. This gives 
overall. - fibonacci heaps: decrease key costs and min-extraction costs . This gives
overall.
Additionally, its space complexity is , assuming adjacency list-based implementation.
In contrast, Floyd-Warshall operates on the adjacency matrix, which is implemented as a 2D array. Its time and space complexity is 
and 
respectively:
4.3. Limitations
Dijkstra’s algorithm may fail to output the correct answer on graphs with negative weight edges.
However, Floyd-Warshall guarantees correctness even when negative weight edges are present. It can also detect negative-weight cycles in the graph.
5. Conclusion
In summary, we’ve explored two seminal shortest path algorithms in this article. We also contrasted them on key parameters.