Dijkstra 算法

该算法维护一组已知从源点到节点的**最短路径**的顶点。图由其**成本邻接矩阵**表示，其中**成本**是边的权重。在图的成本邻接矩阵中，所有对角线值都为零。 如果从源顶点 V_s 到任何其他顶点 V_i 都没有路径，则用 +∞ 表示。在这个算法中，我们假设所有权重都是正数。

1. 最初，集合中没有顶点。
2. 将源顶点 V_s 包含在 S 中。确定从 V_s 到所有其他顶点的所有路径，而无需经过任何其他顶点。
3. 现在，将离 V_s 最近的顶点包含在 S 中，并通过此顶点找到到所有顶点的最短路径并更新值。
4. 重复此步骤，直到在图中包含 n 个顶点的情况下，S 中未包含 n-1 个顶点。

完成该过程后，我们得到了从源顶点到所有顶点的最短路径。

示例： 使用 Dijkstra 算法在图中找到 K 和 L 之间的最短路径，如图所示。

解决方案

步骤 1： 将顶点 K 包含在 S 中，并确定从 K 到所有其他顶点的所有直接路径，而无需经过任何其他顶点。

到所有其他顶点的距离

步骤 2： 将离 K 最近的顶点包含在 S 中，并通过此顶点确定到所有顶点的最短路径并更新值。最近的顶点是 c。

到所有其他顶点的距离

步骤 3： 离 K 第二近的顶点是 9，包含在 S 中。

到所有其他顶点的距离

步骤 4： 离 K 第三近的顶点是 b，包含在 S 中。

到所有其他顶点的距离

步骤 5： 离 K 最近的下一个顶点是 d，包含在 S 中。

到所有其他顶点的距离

由于 S 中包含了 n-1 个顶点。因此，我们找到了从 K 到所有其他顶点的最短距离。因此，K 和 L 之间的最短距离是 8，最短路径是 K, c, b, L。