Dijkstra演算法

习题预习

1. 在下图中，使用Dijkstra’s Algorithm计算从节点A到节点F的最短路径。

2. 节点A、B、C、D、E、F、G连为一棵树，各自与相邻节点间有权重，使用Dijkstra’s Algorithm计算从节点A到节点G的最短路径。

3. 在下图中，使用Dijkstra’s Algorithm计算从节点A到节点J的最短路径。

4. 考虑以下加权连通无向图。使用Dijkstra’s Algorithm计算从节点A到节点I的最短路径。

5. 考虑以下加权有向图。使用Dijkstra’s Algorithm计算从节点A到节点G的最短路径。

请注意，这些问题中的图形可能有其他边或节点，但为了简化问题，它们未显示。对于这些问题，您需要先使用Dijkstra’s Algorithm计算出每个节点到源节点的最短路径。

说明知识

Dijkstra’s Algorithm是一种用于寻找最短路径的演算法，通常用于计算机科学，特别是网路路由和GPS导航等应用中。

这个演算法的主要思想是，寻找从起点到终点的最短距离，如果路径经过的节点有边权重（也称为距离）之和最小，那么该路径就是最短路径。Dijkstra算法通过对整个图进行BFS搜寻，以距离值作为优先顺序，计算出从起点到所有节点的距离。

以下是Dijkstra算法寻找从节点A到节点J的最短路径的步骤：

1. 创建一个距离矩阵，设置所有节点的初始距离为无限大，除了起点，它的距离为0。

2. 选择起点A，并将其加入到一个已访问的集合中。

3. 对A周围可到达节点的距离进行更新，这些节点的距离设置为A的距离加上从A到其它节点的距离。

4. 从距离矩阵中选择距离最短的节点，将其添加到已访问的集合中。

5. 重复3和4，直到所有节点都被检查并且在距离矩阵中更新了最短距离。

以下是一个例子，如图所示，我们要找到从节点A到节点J的最短路径。

1. 创建距离矩阵，设置所有节点的初始距离为无限大，除了起点A，它的距离为0。

2. 选择起点A，将其添加到已访问的集合中。

3. 将起点A的距离更新周围可到达节点的距离，节点D的距离为3，节点B的距离为5，节点C的距离为9。

4. 从距离矩阵中选择距离最短的节点D，将其添加到已访问的集合中。

5. 将节点D的距离更新周围可到达节点的距离，节点E的距离为6，节点B的距离依然是5，节点C的距离为9。

6. 从距离矩阵中选择距离最短的节点B，将其添加到已访问的集合中。

7. 将节点B的距离更新周围可到达节点的距离，节点C的距离为8，节点F的距离为10，节点E的距离为12。

8. 从距离矩阵中选择距离最短的节点C，将其添加到已访问的集合中。

9. 将节点C的距离更新周围可到达节点的距离，节点F的距离为14，节点E的距离为11。

10. 从距离矩阵中选择距离最短的节点E，将其添加到已访问的集合中。

11. 将节点E的距离更新周围可到达节点的距离，节点J的距离为20，节点F的距离为14。

12. 从距离矩阵中选择距离最短的节点F，将其添加到已访问的集合中。

13. 将节点F的距离更新周围可到达节点的距离，节点J的距离为17。

14. 从距离矩阵中选择距离最短的节点J，将其添加到已访问的集合中。

15. 所有节点都已经访问完毕，距离矩阵中显示了从节点A到所有节点的最短距离，节点J的距离为17，因此，从节点A到节点J的最短路径是A->D->E->F->J，距离为17。

这就是Dijkstra算法的基本流程，它可以在有向带权图中找到最短路径。注意，如果图上的边权重为负数，则此算法可能会出现非最优解。

条列重点

1. Dijkstra’s Algorithm是一种最短路径演算法，用于在图中找到从起始点到终点的最短路径。

2. 算法需要有一个起点，并通过不断选择最短路径的方式，来进行扩展以找到终点。

3. 在算法开始之前，必须初始化起点到每一个点的距离值为无限大，起始点的距离值为0。

4. 在每个迭代过程中，从未访问过的点中选择距离起点最近的一个点作为下一个扩展的节点。

5. 在每个点扩展的过程中，计算更新相邻节点的距离值，如果该距离值比之前的值更小，则将它更新为新的值。

6. 继续迭代选择下一个距离起点最近的未访问点，直至找到终点或所有点都已访问。

7. 在算法结束时，通过从终点逆向遍历每一个节点，可以得到起始点到终点的最短路径。

知识测验

1. 给定一个有向带权图，求出从指定起点到所有节点的最短路径。
   答案：Dijkstra演算法可以用来解决这个问题。

2. 给定一个无向带权图，求出从指定起点到其它所有节点的最短路径，每条路径不能经过特定的边。
   答案：可以将需要排除的边权值设为无限大，然后运用Dijkstra演算法求解。

3. 给定一个无向带权图，求出从指定起点到终点的最短路径，其中路径上最大的权值不能超过指定的值。
   答案：可以使用Dijkstra演算法，但要修改权值比较的方式，要以每个节点到起始节点的距离加上指定路径权值作为比较标准。

4. 给定一个有向带权图和一个权值，求出从指定起点到终点，权值恰好为指定值的路径。
   答案：可以使用Dijkstra演算法，但要将所有权值小于指定值的边的权值设为无限大，所有大于指定值的边的权值也设为无限大。

5. 给定一个无向带权图和一个权值K，要求在给定权值范围内满足最少边权值总和的生成树。
   答案：可以将图使用Kruskal演算法生成树后分别使用Dijkstra演算法处理所有生成树的边，从而求出最少权值和。