Dijkstra算法

你在谷歌或者百度地图里面查找过两个地点的最短路径么？Dijkstra算法在GPS网络里面查找两点的最短路径非常的有用。

Dijkstra算法是一个贪婪算法，一步步的找出最短路径，或者最优的方案。在有向图或者无向图中，Dijkstra算法可以找到两个顶点的最短路径。给定一个起点，该算法可以找到到所有顶点的最短路径。

Dijkstra算法运用在多个领域：
1，传染病传播：发现生物疾病传播最快的地方。
2，电话网络：将呼叫路由都网络中可用的最大带宽路径。
3，导航：为旅行者提供最短且最快的路径。

Example

下图为一个有向图，我们将其想象为一个GPS网络。顶点代表实际地点，边表示两点之间所要的花费。 Dijkstra1.png

在Dijkstra算法中，我们需要选中一个顶点作为起点。在这里我们假设顶点A为起点。

第一回合

Dijkstra2.png

从顶点A，查看它的所有外向边，在这个例子，有3条边：

• A 到 B，需要花费 8
• A 到 F，需要花费 9
• A 到 G，需要花费 1
  由于顶点A没有到其他剩余顶点的边，将其标记为 nil。

在上面的例子中，右边的输出表用来记录Dijkstra算法的每一个阶段。每一个回合，该图表将会增加一行。该表的最后一行是该算法的最终输出值。

Second pass

Dijkstra3.png
在下一次循环中，Dijkstra算法将从最小的路径开始，A 到 G 的路径最小 ，值为1，是到G的最短路径。在输出表中，我们将该位置标记为深色。 Dijkstra4.png
现在，沿着最短路径走到 顶点G，查找G的所有外向边。只有一个路径 ：G 到 C，因为 从 A 到 G 到 C，总的花费为 1+ 3 = 4。

输出表里面每一个值由两部分组成 例如 4G,4代表 A到 C的总花费。G代表，从A到C，经过G，且 G为C的邻居顶点。8 A，8 代表 从 A 到 B的总花费为 8，且 A为 B的邻居顶点。nil 代表从A到该顶点没有路径。

第三回合

Dijkstra5.png
在接下来的循环中，我们查找最小花费，根据这个表，我们可以知道 到顶点C的路径花费是最小的。
Dijkstra6.png
观察C的所有外向边：

• C 到 E总的花费为 4 + 1 = 5
• C 到 B总的花费为 4 + 3 = 7
  我们发现从 A -> C -> B 的花费 小于 A -> B的花费，接下来，我们将输出表里面 的 8 A 替换为 7C

第4回合

Dijkstra7.png
在下一次循环中，根据上面的输出表，我们可以看出，除去被标记为深色的，从A -> E的花费最小，为5。接下来，我们会从顶点E接着查找。 Dijkstra8.png

我们将E列填充为深色，E的外向边有3条：

• A-> E -> C: 总的花费为 5 + 8 = 13。由于之前已经找到到C的最短路径（经过顶点G到达C路径最短），所以这次将这条路忽略。
• A -> E -> D: 总的花费为 5 + 2 = 7。
• A -> E ->B: 总的花费为 5+ 1 = 6。根据上面的输出表，经过E到B，比经过C到E的花费要少，所以我们将 7C更新为 6E。

第5回合

Dijkstra9.png

除去标记为深色的，现在B处的花费最少，我们从B点继续查找。

Dijkstra10.png

顶点B有两条外向边：

• B -> E总的花费为 6 + 1 = 7，但是在之前我们已经找到了到E的最短路径（从A经过C到E，总的花费为5），所以我们这次舍弃该路径。
• B -> F总的花费为 6 + 3 = 9，从上面的输出表我们可以看出，从 A->F总的花费也为 9，我们可以舍弃这次查找的结果。

第六回合

Dijkstra11.png
接下来我们将从顶点D进行查找
Dijkstra12.png
然而，顶点D没有外向边，我们只记录下到D的最短路径就可以了。

第7回合

Dijkstra13.png

接下来，从F开始查找

Dijkstra14.png

顶点F只有一个到顶点A的外向边，由于A是起点，所以我们可以忽略此次查找。

第八回合

我们现在的查找已经涵盖了除了顶点H以外的所有顶点，顶点 H 有两条外向边，但是该图中没有任何顶点可以到达H，所以，H那一列里面的值全为 nil。

Dijkstra15.png
现在我们访问了所有顶点，Dijkstra算法完成！！！ Dijkstra16.png
现在我们可以知道从顶点A到任意顶点的最短路径和最小花费了，举个例子，A -> D的最小花费为 7，我们可以对表格进行回溯，就可以查找到该路径，D -> E -> C -> G-> A

实现

为了实现Dijkstra算法，我们需要用到邻接图和优先级队列。
优先级队列用来存储已经访问过的顶点，优先级队列是最小优先级队列，当每次出队的时候都会将路径最短的边出队。

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
  }
}

辅助方法

在构建Dijkstra算法之前，我们先创建几个辅助方法。

回溯到起始顶点

Dijkstra17.png
我们需要一个机制来记录从当前顶点回到起始顶点的总的权重。我们定义一个叫 paths的字典来存储每一个顶点的 Visit 状态。

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字典作为参数，paths构建了到达目的顶点的路径。
1，从目的顶点开始。
2，创建了一个存放 path 的数组。
3，只要没有到达起始顶点，就继续取出下一条边。
4，将边加到数组中。
5，对路径进行回溯，将边的起始顶点设置为当前顶点，这样就离起始顶点更近了。
6，当循环到达到起始顶点时，就完成了目的顶点到起始顶点的路径查找。

计算总的距离

Dijkstra18.png
既然我们可以得到从目的顶点到起始顶点的路径，那么，我们就可以根据这个路径计算出该路径需要的总的花费。我们在 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
}

该方法以目的顶点和已存在的路径字典为参数，最后将总的花费返回。
1，得出起始顶点到目的顶点的全部路径。
2，在 path 数组中，删除权重为 nil 的边。
3，使用 reduce 计算边的总的权重。

最短路径

在 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 顶点为参数，最后以字典的形式返回从起始顶点到各个顶点的路径集合：
1，初始化 paths 字典， 并且将 起始 顶点添加到字典中。
2，创建最小优先级队列来存储已访问的顶点，已顶点到起始顶点的路径总和为优先级。
3，将起始顶点入队，起始顶点为访问的第一个顶点。

完善 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

1，我们会一直使用 Dijkstra 算法去寻找最短路径的集合，直到访问完所有的顶点为止。一旦队列为空，就说明我们已经访问完所有的顶点。
2，遍历顶点的所有边。
3，确保每一条边都有权值。
4，如果 destination 顶点没有被访问过，或者，已经找到更短的路径，我们就更新 paths 字典并将该路径的目的顶点入队。

寻找到指定顶点的最短路径

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

最后附上本文的相关代码DataAndAlgorim

参考链接《Data Structures & Algorithms in Swift》