1 图的最短路径

给定一个图和图中的源顶点，查找从源到给定图中所有顶点的最短路径。

Dijkstra的算法与Prim的最小生成树算法非常相似。像Prim的MST一样，我们生成一个以给定源为根的SPT（最短路径树）。我们维护两个集合，一个集合包含最短路径树中包含的顶点，另一个集合包含最短路径树中尚未包含的顶点。在算法的每个步骤中，我们都会找到另一个集合（尚未包含的集合）中的顶点，该顶点与源之间的距离最小。

下面是Dijkstra算法中使用的详细步骤，用于查找从单个源顶点到给定图中所有其他顶点的最短路径。

2 算法

1） 创建一个集sptSet（最短路径树集），用于跟踪最短路径树中包含的顶点，即计算并最终确定其与源的最小距离。最初，此集合为空。

2） 为输入图形中的所有顶点指定距离值。将所有距离值初始化为无穷大。将源顶点的距离值指定为0，以便首先拾取该顶点。

3） 而sptSet不包括所有顶点

….a） 拾取sptSet中不存在且具有最小距离值的顶点u。

….b） 包括u到sptSet。

….c） 更新u的所有相邻顶点的距离值。若要更新距离值，请遍历所有相邻顶点。对于每个相邻顶点v，如果u（从源）的距离值和边u-v的权重之和小于v的距离值，则更新v的距离值。