Data Structures Algorithms 简明教程

Dijkstra’s Shortest Path Algorithm

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

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

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

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

声明两个数组 − distance[] 和 visited[] 分别用于存储图中源顶点到其他顶点的距离以及已访问的顶点。
将 distance[S] 设置为“0”，将 distance[v] 设置为无穷大，其中 v 表示图中的所有其他顶点。
将 S 添加到 visited[] 数组中，找出具有最小距离的 S 的相邻顶点。
假设 S 的相邻顶点为 A，且具有最小距离，且尚未出现在 visited 数组中。选择 A 并将其添加到 visited 数组中，然后将 A 的距离从无穷大更改为已分配的距离 A，即 d1，其中 d1 < 无穷大。
重复此过程，找出已访问顶点的相邻顶点，直至形成最短路径生成树。

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

Step 1

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

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

visited = {S}

Step 2

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

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

Visited = {S, A}

Step 3

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

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

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

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）的距离，选择距离最小的顶点。

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

Visited = {S, A, E, D}

Step 5

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

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

dist[C] = 最小值 (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

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

Step 6

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

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

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

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