第42章：Dijkstra算法

你是否使用过谷歌或苹果地图应用来寻找从一个地方到另一个地方的最短距离或最快时间？Dijkstra算法在GPS网络中特别有用，可以帮助找到两个地方之间的最短路径。

Dijkstra算法是一种贪婪的算法。贪婪算法是一步一步地构建一个解决方案，它在每一步都孤立地挑选出最理想的路径。它错失了一些步骤可能花费更多，但整体成本更低的解决方案。尽管如此，它通常很快就能得到一个相当好的解决方案。

Dijkstra算法在有向图或无向图的顶点之间寻找最短路径。给定图形中的一个顶点，该算法将找到从起始顶点出发的所有最短路径。

Dijkstra算法的其他一些应用包括。

  1. 传染性疾病的传播。发现生物疾病在哪里传播得最快。

  2. 电话网络。将呼叫路由到网络中可用的最高带宽路径。

  3. 绘图。为旅行者寻找最短和最快的路径。

例子

到目前为止，你所看到的所有图都是无向图。让我们稍微改变一下，用一个有向图来工作! 想象一下，下面的有向图代表一个GPS网络。

顶点代表物理位置，边代表位置之间给定成本的单程路径。

在Dijkstra算法中，你首先要选择一个起始顶点，因为该算法需要一个起点来寻找通往图中其他节点的路径。假设你选择的起始顶点是顶点A。

第一道程序

从顶点A开始，查看所有出站的边。在这种情况下，你有三条边。

其余的顶点将被标记为nil，因为从A到它们没有直接的路径。

当你通过这个例子时，图右边的表格将代表Dijkstra算法在每个阶段的历史，或记录。算法的每一次传递都会在表格中增加一行。表中的最后一行将是算法的最终输出。

第二遍

在下一个循环中，Dijkstra算法会查看你到目前为止的最低成本路径。A到G的最小成本是1，也是到达G的最短路径。这条路径在输出表中用深色填充物标记。

现在，从成本最低的路径，即顶点G，看一下所有的出站边。只有一条从G到C的边，其总成本是4。到C的成本是1+3=4。

输出表中的每个值都有两个部分：到达该顶点的总成本和通往该顶点路径上的最后一个邻居。例如，顶点C一栏中的数值4 G意味着到达C的成本是4，并且到达C的路径要经过G。

第三遍

在下一个循环中，你看一下下一个最低成本。根据表格，到C的路径成本最小，所以搜索将从C继续进行。

看一下C的所有出站边。

你已经找到了一条到B的成本较低的路径，所以你替换了之前的B的值。

第四遍

现在，在下一个循环中，问自己下一个成本最低的路径是什么？根据表格，C到E的总成本最小，为5，所以将从E继续搜索。

你填补了E列，因为你已经找到了最短的路径。顶点E有以下出站边。

第五遍

接下来，你从B继续搜索。

B有这些出去的边。

第六遍

在下一个循环中，你继续从D开始搜索。

然而，D没有出站边，所以它是一个死胡同。你记录下你已经找到了通往D的最短路径并继续前进。

第七遍

接下来是F。

F有一条通往A的出线，总成本为9+2=11。你可以不考虑这条边，因为A是起始顶点。

第八遍

你已经覆盖了每一个顶点，除了H。H有两条出站边到G和F，然而从A到H没有路径。

这一步完成了Dijkstra的算法，因为所有的顶点都已经被访问过了

现在你可以检查最后一行的最短路径和它们的成本。例如，输出告诉你到达D的成本是7。 要找到路径，你要回溯。每一列记录了当前顶点所连接的前一个顶点。你应该从D到E到C到G，最后回到A。

实现

打开本章的启动游戏场。这个操场带有一个邻接列表图和一个优先级队列，你将用它来实现Dijkstra算法。

优先级队列用于存储尚未被访问的顶点。它是一个最小优先级队列，所以每次当你取消一个顶点时，它都会给你当前暂定最短路径的顶点。

打开Dijkstra.swift，添加以下内容。

public enum Visit<T: Hashable> { 
  case start // 1 
  case edge(Edge<T>) // 2 
}

在这里，你定义了一个名为Visit的枚举。这个类型记录了两种状态。

  1. 顶点是起始顶点。

  2. 顶点有一条相关的边，它导致了一条回到起始顶点的路径。

现在，定义一个名为Dijkstra的类。在你上面添加的代码后面添加以下内容。

public class Dijkstra<T: Hashable> {

  public typealias Graph = AdjacencyList<T>
  let graph: Graph

  public init(graph: Graph) { 
    self.graph = graph 
  }
}

如同前一章，Graph被定义为AdjacencyList的类型别名。如果需要的话，你可以在将来用一个邻接矩阵来代替它。

帮助方法

在构建Dijkstra之前，让我们创建一些帮助方法，以帮助创建算法。

追溯到起点

你需要一个机制来跟踪从当前顶点回到起始顶点的总重量。为了做到这一点，你将跟踪一个名为paths的字典，它为每个顶点存储一个Visit状态。

在Dijkstra类中添加以下方法。

这个方法接收了目标顶点和现有路径的字典，并构建了一条通往目标顶点的路径。浏览一下代码。

  1. 从目标顶点开始。

  2. 创建一个边的数组来存储路径。

  3. 只要你没有到达开始的情况，继续提取下一条边。

  4. 将这条边添加到路径上。

  5. 将当前顶点设置为这条边的源顶点。这个任务使你更接近起始顶点。

  6. 一旦while循环到达起始情况，你就完成了路径并返回。

计算总距离

一旦你有能力构建一条从目的地回到起始顶点的路径，你需要一种方法来计算该路径的总重量。在Dijkstra类中添加以下方法。

这个方法接收目的地顶点和现有路径的字典，并返回总重量。翻阅代码。

  1. 构建通往目标顶点的路径。

  2. compactMap从路径中删除所有无效的权重值。

  3. reduce将所有边的权重相加。

现在你已经建立了辅助方法，你可以实现Dijkstra的算法。

生成最短路径

在距离方法之后，添加以下内容。

这个方法接收一个起始顶点，并返回一个所有路径的字典。在这个方法中，你

  1. 定义路径，并用起始顶点初始化它。

  2. 创建一个最小优先级的队列来存储必须访问的顶点。排序闭包使用你创建的距离方法对顶点按其与起始顶点的距离进行排序。

  3. 将起始顶点作为第一个要访问的顶点进行排队。用以下方法完成shortestPath的实现。

翻阅代码。

  1. 你继续用Dijkstra的算法寻找最短路径，直到所有的顶点都被访问过。当优先级队列为空时，你知道你已经完成了。

  2. 对于当前的顶点，你通过它所有的邻接边。

  3. 确保该边有一个权重。如果没有，你就转到下一条边。

  4. 如果目标顶点之前没有被访问过，或者你已经找到了一条更便宜的路径，你就更新路径，并将相邻的顶点添加到优先级队列中。

一旦所有顶点都被访问过，而且优先级队列是空的，你就会返回到起始顶点的最短路径字典。

寻找一个特定的路径

在Dijkstra类中添加以下方法。

这个方法接收目的地顶点和最短路径的字典，并返回到目的地顶点的路径。

尝试一下你的代码

导航到主操场，你会发现上面的图已经用邻接列表构建好了，可以看到Dijkstra的算法在运行。

将以下代码添加到操场页面。

在这里，你通过传入图网络创建一个Dijkstra的实例，并做以下工作。

  1. 计算从起始顶点A到所有顶点的最短路径。

  2. 得到通往D的最短路径。

  3. 打印这个路径。

这样的输出结果。

A --|1.0|--> G 
G --|3.0|--> C 
C --|1.0|--> E 
E --|2.0|--> D

表现

在Dijkstra的算法中，你使用邻接列表构建了你的图。你用一个最小优先级队列来存储顶点并提取具有最小路径的顶点。这个过程的总体时间复杂度为O(log V)。提取最小元素或插入一个元素的堆操作都分别需要O(log V)。

如果你还记得广度优先搜索一章，遍历所有顶点和边需要O(V + E)。Dijkstra的算法有点类似于广度优先搜索，因为你必须探索所有相邻的边。这一次，你不是下到下一级，而是使用最小优先级队列来选择距离最短的单个顶点来向下遍历。这意味着它是O(1+E)或简单的O(E)。因此，将遍历与对最小优先级队列的操作相结合，执行Dijkstra算法需要O(E log V)。

关键点

上一章 目录 下一章