Data Structures Algorithms 简明教程

Dijkstra’s Shortest Path Algorithm

Dijkstra 的最短路径算法类似于 Prim 的算法，因为它们都依赖于在局部找到最短路径以实现全局解决方案。然而，与 Prim 的算法不同，Dijkstra 的算法不会找出最小生成树；它旨在从一个顶点找到图中到图中其他剩余顶点的最短路径。Dijkstra 的算法可以在有向图和无向图上执行。

Dijkstra’s shortest path algorithm is similar to that of Prim’s algorithm as they both rely on finding the shortest path locally to achieve the global solution. However, unlike prim’s algorithm, the dijkstra’s algorithm does not find the minimum spanning tree; it is designed to find the shortest path in the graph from one vertex to other remaining vertices in the graph. Dijkstra’s algorithm can be performed on both directed and undirected graphs.

由于可以从单个源顶点计算到图中所有其他顶点的最短路径，Dijkstra 算法也称为 single-source shortest path algorithm 。获得的输出称为 shortest path spanning tree 。

Since the shortest path can be calculated from single source vertex to all the other vertices in the graph, Dijkstra’s algorithm is also called single-source shortest path algorithm. The output obtained is called shortest path spanning tree.

在本节中，我们将学习 Dijkstra 算法的贪婪方法。

In this chapter, we will learn about the greedy approach of the dijkstra’s algorithm.

Dijkstra’s Algorithm

Dijkstra 算法旨在找出图中两个顶点之间的最短路径。这两个顶点既可以相邻，也可以是图中最远的点。该算法从源开始。该算法获取的输入为图 G {V, E}，其中 V 是顶点集，E 是边集，以及源顶点 S。且输出为最短路径生成树。

The dijkstra’s algorithm is designed to find the shortest path between two vertices of a graph. These two vertices could either be adjacent or the farthest points in the graph. The algorithm starts from the source. The inputs taken by the algorithm are the graph G {V, E}, where V is the set of vertices and E is the set of edges, and the source vertex S. And the output is the shortest path spanning tree.

Algorithm

Declare two arrays − distance[] to store the distances from the source vertex to the other vertices in graph and visited[] to store the visited vertices.
Set distance[S] to ‘0’ and distance[v] = ∞, where v represents all the other vertices in the graph.
Add S to the visited[] array and find the adjacent vertices of S with the minimum distance.
The adjacent vertex to S, say A, has the minimum distance and is not in the visited array yet. A is picked and added to the visited array and the distance of A is changed from ∞ to the assigned distance of A, say d1, where d1 < ∞.
Repeat the process for the adjacent vertices of the visited vertices until the shortest path spanning tree is formed.

Examples

为了更好地理解 Dijkstra 的概念，让我们通过示例图来分析该算法 −

To understand the dijkstra’s concept better, let us analyze the algorithm with the help of an example graph −

Step 1

将所有顶点的距离初始化为无穷大，源节点 S 除外。

Initialize the distances of all the vertices as ∞, except the source node S.

现在，源顶点 S 已访问，将其添加到 visited 数组中。

Now that the source vertex S is visited, add it into the visited array.

visited = {S}

Step 2

顶点 S 有三个具有不同距离的相邻顶点，其中距离最小的顶点为 A。因此，A 已访问，且 dist[A] 已从无穷大更改为 6。

The vertex S has three adjacent vertices with various distances and the vertex with minimum distance among them all is A. Hence, A is visited and the dist[A] is changed from ∞ to 6.

S → A = 6
S → D = 8
S → E = 7

Visited = {S, A}

Step 3

已访问 visited 数组中的两个顶点，因此必须为这两个已访问顶点检查相邻顶点。

There are two vertices visited in the visited array, therefore, the adjacent vertices must be checked for both the visited vertices.

顶点 S 还有两个相邻顶点尚未访问，即 D 和 E。顶点 A 有一个相邻顶点 B。

Vertex S has two more adjacent vertices to be visited yet: D and E. Vertex A has one adjacent vertex B.

计算从 S 到 D、E、B 的距离，选择最小距离 −

Calculate the distances from S to D, E, B and select the minimum distance −

S → D = 8 and S → E = 7.
S → B = S → A + A → B = 6 + 9 = 15

Visited = {S, A, E}

Step 4

计算 visited 数组中所有已访问顶点的相邻顶点（S、A、E）的距离，选择距离最小的顶点。

Calculate the distances of the adjacent vertices – S, A, E – of all the visited arrays and select the vertex with minimum distance.

S → D = 8
S → B = 15
S → C = S → E + E → C = 7 + 5 = 12

Visited = {S, A, E, D}

Step 5

重新计算未访问顶点的距离，如果找到比现有距离更小的最小距离，则在 distance 数组中替换该值。

Recalculate the distances of unvisited vertices and if the distances minimum than existing distance is found, replace the value in the distance array.

S → C = S → E + E → C = 7 + 5 = 12
S → C = S → D + D → C = 8 + 3 = 11

dist[C] = 最小值 (12, 11) = 11

dist[C] = minimum (12, 11) = 11

S → B = S → A + A → B = 6 + 9 = 15
S → B = S → D + D → C + C → B = 8 + 3 + 12 = 23

dist[B] = 最小值 (15,23) = 15

dist[B] = minimum (15,23) = 15

Visited = { S, A, E, D, C}

Step 6

图中剩余的未访问顶点是 B，最小距离为 15，被加入到输出生成树中。

The remaining unvisited vertex in the graph is B with the minimum distance 15, is added to the output spanning tree.

Visited = {S, A, E, D, C, B}

最短路径生成树使用 Dijkstra 算法作为输出获得。

The shortest path spanning tree is obtained as an output using the dijkstra’s algorithm.

Example

该程序实现 Dijkstra 的最短路径问题，该问题将成本邻接矩阵作为输入，并将最短路径以及最小成本打印为输出。

The program implements the dijkstra’s shortest path problem that takes the cost adjacency matrix as the input and prints the shortest path as the output along with the minimum cost.