Dijkstra算法为什么使用键值递减？

Dijkstra算法是一种用于找出图中单个源点到其他所有点的最短路径的算法。这种算法特别适用于基于权重的有向和无向图。Dijkstra算法使用键值递减的策略，主要是为了更有效地找到最短路径。下面我将详细解释这一点。

键值的作用

在Dijkstra算法中，键值（通常是距离）用于记录从源点到图中各点的最短距离的当前估计值。算法开始时，源点的键值设为0（因为源点到自己的距离是0），而其他所有点的键值设为无穷大（表示初始时，源点到这些点的距离未知）。

为什么使用键值递减

在算法的每一步中，都会从尚未处理的顶点中选择一个键值最小的顶点（即当前估计的最短距离最小的顶点）。然后，算法探索这个顶点的所有邻接点，更新到这些邻接点的距离（键值）。这个更新是基于当前选择的顶点的键值加上从这个顶点到其邻接点的边的权重。

这里的关键是：如果找到了一个更短的路径到某个顶点（即通过当前顶点到其邻接点的距离比之前记录的键值还要小），那么就需要更新这个邻接点的键值。这就是所谓的键值递减。

例子

假设有一个图，A、B、C是图中的顶点，其中A是源点。假设A到B的直接距离是10，而A到C的直接距离是5，C到B的距离是3。

1. 初始时，A的键值是0，B和C的键值是无穷大。
2. 选择键值最小的顶点A，更新A的邻接点B和C的键值。B的新键值是10，C的新键值是5。
3. 接下来选择键值最小的顶点C（键值为5）。检查C的邻接点，发现通过C到B的路径长度是5 + 3 = 8，小于之前B的键值10，因此将B的键值更新为8。
4. 此时B的键值已由10递减到8，显示了键值递减的过程。

通过这种方式，Dijkstra算法确保了每次选取的顶点都是当前未处理顶点中最有可能达到最短路径的顶点，并通过逐步递减键值来有效更新和优化路径长度。这种递减策略是算法保证能找到所有顶点最短路径的核心部分。