42.`Dijkstra`的算法¶

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

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

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

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

传染性疾病的传播：发现生物疾病在哪里传播得最快。
电话网络：将呼叫路由到网络中可用的最高带宽路径。
绘图：为旅行者寻找最短和最快的路径。

示例¶

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

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

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

第一遍¶

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

A到B的成本是8。
A到F的成本是9。
A到G的成本为1。

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

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

第二遍¶

在下一个循环中，Dijkstra的算法着眼于你迄今为止拥有的lowest成本的路径。A到G的成本最小为1，也是到达G的最短路径。这个路径在输出表中被标记为深色填充。

现在，从成本最低的路径，vertex G，看看所有的出线。只有一条从G到C的边，其总成本是4。这是因为从A到G到C的成本是1 + 3 = 4。

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

第三遍¶

在下一个循环中，你看下一个最低的成本。根据表格，到C的路径成本最小，因此将从C继续搜索。你填补了C列，因为你已经找到了到达C的最短路径。

看一下C的所有出站边：

C到E的总成本是4 + 1 = 5。
C到B的总成本是4 + 3 = 7。

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

第四遍¶

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

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

E到C的总成本为5+8=13。因为你已经找到了到C的最短路径，所以不考虑这个路径。
E到D的总成本是5 + 2 = 7。
E到B的总成本为5 + 1 = 6。根据表格，当前到B的最短路径的总成本为7。你更新从E到B的最短路径，因为它的成本较小，为6。

第五遍¶

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

B有这些出去的边：

B到E的总成本是6 + 1 = 7，但是你已经找到了到E的最短路径，所以不考虑这个路径。
B到F的总成本是6 + 3 = 9。从表中可以看出，目前从A到F的路径也需要花费9。你可以不考虑这个路径，因为它并不短。

第六遍¶

在下一个周期，你继续从D开始搜索。

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

第七遍¶

接下来是F。

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

第八遍¶

你已经覆盖了每个顶点，除了H。H有两条出线到G和F。然而，从A到H没有路径。因为没有路径，所以H的整列是nil。

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

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

实施¶

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

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

打开Dijkstra.swift并添加以下内容：

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

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

顶点是起始顶点。
顶点有一个相关的edge，通往回到起始顶点的路径。

现在，定义一个名为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类中添加以下方法：

private func route(to destination: Vertex<T>,
                   with paths: [Vertex<T> : Visit<T>]) -> [Edge<T>] {
  var vertex = destination // 1
  var path: [Edge<T>] = [] // 2

  while let visit = paths[vertex], case .edge(let edge) = visit { // 3
    path = [edge] + path // 4
    vertex = edge.source // 5
  }
  return path // 6
}

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

从destination顶点开始。
创建一个边的数组来存储路径。
只要你没有达到start的情况，继续提取下一个edge。
将这条边添加到路径中。
将当前顶点设置为该边的source顶点。这个赋值使你更接近于起始顶点。
一旦while循环到达start情况，你就完成了路径并返回。

计算总距离¶

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

private func distance(to destination: Vertex<T>,
                      with paths: [Vertex<T> : Visit<T>]) -> Double {
  let path = route(to: destination, with: paths) // 1
  let distances = path.compactMap { $0.weight } // 2
  return distances.reduce(0.0, +) // 3
}

这个方法接收destination顶点和现有paths的字典，并返回总重量。浏览一下代码：

构建通往destination顶点的路径。
compactMap从paths中删除所有nil的权重值。
reduce对所有边的权重进行求和。

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

生成最短路径¶

在distance方法之后，添加以下内容：

public func shortestPath(from start: Vertex<T>) -> [Vertex<T> : Visit<T>] {
  var paths: [Vertex<T> : Visit<T>] = [start: .start] // 1

  // 2
  var priorityQueue = PriorityQueue<Vertex<T>>(sort: {
    self.distance(to: $0, with: paths) <
    self.distance(to: $1, with: paths)
  })
  priorityQueue.enqueue(start) // 3

  // to be continued
}

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

定义paths，并用start顶点初始化它。
创建一个最小优先级的队列来存储必须访问的顶点。sort闭包使用你创建的distance方法，根据顶点与start顶点的距离进行排序。
将start顶点作为第一个要访问的顶点进行排队。

完成你的shortestPath的实现：

while let vertex = priorityQueue.dequeue() { // 1
  for edge in graph.edges(from: vertex) { // 2
    guard let weight = edge.weight else { // 3
      continue
    }
    if paths[edge.destination] == nil ||
       distance(to: vertex, with: paths) + weight <
       distance(to: edge.destination, with: paths) { // 4
      paths[edge.destination] = .edge(edge)
      priorityQueue.enqueue(edge.destination)
    }
  }
}

return paths

翻阅代码：

你继续用Dijkstra的算法寻找最短路径，直到所有的顶点都被访问过。当优先级队列为空时，你知道你已经完成了。
对于当前的vertex，你通过其所有相邻的边。
确保该边有一个权重。如果没有，你就转到下一条边。
如果destination顶点之前没有被访问过，或者你已经找到了一条更便宜的路径，你就更新路径，并将相邻的顶点添加到优先队列中。

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

寻找一个特定的路径¶

在Dijkstra类中添加以下方法：

public func shortestPath(to destination: Vertex<T>,
                         paths: [Vertex<T> : Visit<T>]) -> [Edge<T>] {
  return route(to: destination, with: paths)
}

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

试用你的代码¶

导航到主playground，你会注意到上面的图已经用邻接列表构建好了，可以看到Dijkstra的算法在发挥作用。

在playground页面上添加以下代码：

let dijkstra = Dijkstra(graph: graph)
let pathsFromA = dijkstra.shortestPath(from: a) // 1
let path = dijkstra.shortestPath(to: d, paths: pathsFromA) // 2
for edge in path { // 3
  print("\(edge.source) --|\(edge.weight ?? 0.0)|--> \(edge.destination)")
}

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

计算从起始顶点A到所有顶点的最短路径。
获得到D的最短路径。
打印这个路径。

这个产出：

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)。

关键点¶

Dijkstra算法在给定一个起始顶点的情况下，找到一条通往其余节点的路径。
这种算法对于寻找不同端点之间的最短路径非常有用。
Visit状态被用来跟踪回到起始顶点的边。
优先级队列数据结构确保返回具有最短路径的顶点。
因为它在每一步都选择最短的路径，所以说它是贪婪的!

42.Dijkstra的算法¶

示例¶