算法描述 该算法维护了两个点集，S和V。其中S集合为已经确定到源点最短路径的点集，V集合为未确定到源点最短路径的点集。 循环进行以下操作直到所有点都确定了与源点的最短路径：从V集合中取出一点，使得该点到源点距离为V集合中最短。然后通过该点，更新与该点相连的点距离源点的距离。最后，将该点放入S集合中。 算法正确性 该算法最关键的步骤就是从V集合中取点的操作。设i为V集合中一点，j为V集合中任意其他一点，dis[i]<dis[j]，则dis[i]<dis[j]+a[j][i]，故点i距离源点距离为确定值。其中dis[i]为源点到点i的最短路径，a[j][i]为点j到点i的距离。 由于我们需要取一个已经确定了与源点最短路径的点，如果取出的点的dis[i]并不是最小的，那么其他点是可以更新该点的，也就是说该点距离源点的最短路径并不是确定的。相反，如果dis[i]小于集合V中的任何其他点到源点的距离，那么集合V中的其他点一定不能更新dis[i]使dis[i]更小，则点v距离源点的距离dis[i]一定是确定的。 一些不足 首先，dijkstra算法得以成立的前提是从V集合中取出的点距离 ...