43.Dijkstra的算法挑战

挑战1：分步图

给出以下图形，通过Dijkstra算法，从vertex A开始，产生通往其他每个顶点的最短路径。提供上一章所示的最后的路径表。

挑战2：寻找所有最短路径

在Dijkstra类中增加一个方法，返回一个给定起始顶点到所有顶点的最短路径的字典。下面是方法的签名，让你开始使用：

public func getAllShortestPath(from source: Vertex<T>)
                               -> [Vertex<T> : [Edge<T>]] {
    var pathsDict = [Vertex<T> : [Edge<T>]]()

    // Implement Solution Here

    return pathsDict
}

解决方案

挑战1的解决方案

• 到B的路径：A-(1)-B。
• 到C的路径：A-(1)-B-(8)-C。
• 到D的路径：A-(1)-B-(9)-D。
• 到E的路径：A-(1)-B-(8)-C-(2)-E。

挑战2的解决方案

这个函数是Dijkstra.swift的一部分。要得到从source顶点到图中其他每个顶点的最短路径，请执行以下步骤：

public func getAllShortestPath(from source: Vertex<T>)
                               -> [Vertex<T> : [Edge<T>]] {
  var pathsDict = [Vertex<T> : [Edge<T>]]() // 1
  let pathsFromSource = shortestPath(from: source) // 2
  for vertex in graph.vertices { // 3
    let path = shortestPath(to: vertex, paths: pathsFromSource)
    pathsDict[vertex] = path
  }
  return pathsDict // 4
}

1. 字典中存储了从source顶点到每个顶点的路径。
2. 执行Dijkstra算法，从source顶点找到所有的路径。
3. 对于图中的每个顶点，生成source顶点到图中每个顶点之间的边的列表。
4. 返回路径的字典。