Dijkstra 算法 vs Floyd-Warshall 算法

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, t****he key idea is to find the path with the minimum distance between pairs of nodes:

Rendered by QuickLaTeX.com

In the above example, $V = \{A, B, C\}$ and $E = \{A-B, B-C, C-A\}$ . 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 O(V) , 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 O(V^3) and O(V^2) respectively: