Dijkstra - Dijkstra算法
问题
假设图中顶点可以到达任意其他顶点，用Dijkstra算法求顶点到其他所有顶点的最短距离。
解法
设为顶点到的边的距离，数组表示从顶点到的最短距离。
初始时，顶点到自己的距离为0（即），到其他顶点的距离为无穷大；
类似BFS算法，初始时将加入队列中并染红。当不为空时，从中取出头节点，遍历其所有未被染红的邻节点，通过松弛操作更新到的所有邻节点（设邻节点为）的最短距离，并将访问过的邻节点染红：
若，则更新距离；
若，则更新距离；
通过这种BFS算法将图中所有顶点都访问过后，算法结束。顶点到任意其他顶点的最短距离为。该算法时间复杂度为，其中表示平均每个顶点的临边数量。