狄克斯特拉算法

　　狄克斯特拉算法用来找到加权图中的最短路径。
　　广度优先搜索可以找到段数最少的路径，但是如果我们要找到用时最少的路径，就要使用狄克斯特拉算法（Dijkstra’sAlgorithm）。
　　狄克斯特拉算法的使用思路
　　下面这张图中，每个数字表示的都是时间，单位分钟。为找出从起点到终点耗时最短的路径，我们需要使用狄克斯特拉算法。
　　如果使用广度优先搜索，将得到下面这条段数最少的路径。
　　这条路径耗时7分钟。下面来看看能否找到耗时更短的路径。
　　狄克斯特拉算法包含4个步骤：找出最便宜的节点，即可在最短时间内到达的节点。更新该节点的邻居的开销，其含义将稍后介绍。重复这个过程，直到对图中的每个节点都这样做了。计算最终路径。
　　第一步：找出最便宜的节点。你站在起点，不知道该前往节点A还是前往节点B。前往这两个节点都要多长时间呢？
　　前往节点A需要6分钟，而前往节点B需要2分钟。至于前往其他节点，我们暂且还不知道需要多长时间。
　　由于我们还不知道前往终点需要多长时间，因此先假设为无穷大。节点B是最近的2分钟就能达到。
　　第二步：计算经节点B前往其各个邻居所需的时间。
　　这时，我们发现了到A点和终点的更短时间，前往A点的时间从6分钟缩短到5分钟，前往重点的时间降低到7分钟。然后我们就把这两个新的更短的时间更新到表格中。
　　第三步：重复。
　　重复第一步，找出可在最短时间内前往的节点。我们已经对节点B执行了前两步，除节点B外，可在最短时间内前往的节点是节点A。
　　重复第二步，更新节点A的所有邻居的开销：
　　这时我们发现从节点A前往终点的时间只需要6分钟！
　　至此，我们对每个节点都运行了狄克斯特拉算法（无需对终点这样做）。现在，我们知道：前往节点B需要2分钟；前往节点A需要5分钟；前往终点需要6分钟。
　　这时我们发现从节点A前往终点的时间只需要6分钟！
　　最后一步，计算得到最终路径。
　　如果使用广度优先搜索，找到的最短路径将不是这条。因为这条路径包含3段，而有一条从起点到终点的路径只有2段。
　　使用广度优先搜索可以査找两点之间的最短路径。这里的最短路径的意思是段数最少。在狄克斯特拉算法中，我们给每段都分配了一个数字或权重，因此狄克斯特拉算法找出的是总权重最小的路径。狄克斯特拉算法流程小结
　　狄克斯特拉算法包含4个步骤：找到最便宜的节点，即从起点开始，可在最短时间内前往的节点；对于该节点的邻居，检査是否有前往它们的更短路径，如果有，就更新其开销；重复这个过程，直到对图中的每个节点都这样做了，终点是不需要计算的；计算最终路径。