Dijkstra算法，中文翻译为迪杰斯特拉算法，是在带权有向图G = (V, W) （V是节点的集合，W是边上权值的集合，在集合W中，不直接相连的节点间的距离标记为无穷大）中求某个节点到其余节点之间最短路径的经典算法。该算法的核心思想是将图中所有的节点划分为2个集合，集合S包含已经找到最短路径的节点，集合U包含尚未找到最短路径的节点的距离（初始值全部设定为无穷大）。从某一点v开始采用广度优先遍历思想对图进行遍历，每找到一个节点的最短路径，就将该节点从集合U中移除，并加入到集合S中，直到最后U变为空集，S包含图中所有的节点到出发点的最小距离。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长… Read more