Java实现Dijkstra最短路径寻径算法

Dijkstra最短路径算法的基本思想是通过计算图G中的最短路径，需要指定起点vs。引入两个集合S和U，其中S记录已求出最短路径的顶点，U记录还未求出最短路径的顶点及其到起点vs的距离。初始时，S中只有起点vs，U中包含除vs外的所有顶点，且U中顶点的路径为“起点vs到该顶点的路径”。然后，从U中找出路径最短的顶点加入S，更新U中的顶点和路径。重复该操作直到遍历完所有顶点。操作步骤包括：初始时，S只包含起点vs，U包含除vs外的其他顶点，且U中顶点的距离为“起点vs到该顶点的距离”。从U中选出距离最短的顶点k加入S，同时从U中移除顶点k。更新U中各个顶点到起点vs的距离。更新的原因是上一步中确定了k是求出最短路径的顶点。