第43章：Dijkstra算法进阶

挑战1：分步图

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

挑战2：找到所有的最短路径

在Dijkstra类中添加一个方法，返回一个字典，其中包含从一个起始顶点到所有顶点的所有最短路径。下面是方法的签名，让你开始吧。

解决方案

挑战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的一部分。要获得从源顶点到图中其他所有顶点的最短路径，请执行以下操作。

1. 这个字典存储了从源顶点到每个顶点的路径。

2. 执行Dijkstra算法，找到从源顶点出发的所有路径。

3. 对于图中的每个顶点，生成源顶点到图中每个顶点之间的边的列表。

4. 返回路径的字典。

---

上一章	目录	下一章