Dijkstra被证明具有普遍最优性
- 前言
- 举例子
- 总结
前言
具备普遍最优性意思，就是不论该算法面对多复杂的结构，即便在最坏的情况下都能达到理论上的最优性能。一言蔽之，现在的Dijkstra算法，已经被证明是解决单源最短路径问题的“近乎理想”的方法。
举例子
首先，我们先通过一个例子，简单回顾一下Dijkstra算法。
如下图所示，Dijkstra算法寻找最短路径的方法，大致可以分为四步：
从起点出发：选择起点A。计算从A到邻近点的距离，例如到B的距离为1，到C的距离为5。选择较短的路径，即先前往B。
继续探索：从新的点（B）继续查找邻近点的距离，并将这些距离加上从A到B的距离。例如，从A到B的距离是1，B到D的距离是1，因此A到D的总距离为2（1 + 1 = 2）。更新已知的最短路径。
记录新的最短路径：在探索过程中发现更短的路径时，更新记录。例如，A到C的原始距离是5，但通过B和D的路径到C的总距离是3（1 + 1 + 1 = 3），比原来的距离短，因此更新A到C的距离为3。
重复步骤，直到覆盖所有点：算法继续遍历，
