11.2.3 戴克斯特拉算法（Dijkstra’s Algorithm）
戴克斯特拉算法（Dijkstra’s Algorithm）是由荷兰计算机科学家艾兹赫尔·戴克斯特拉Edsger Wybe Dijkstra）发明的。算法解决的是有向图中单个源点到其他顶点的最短路径问题举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径。
在Dijkstra算法的输入中包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。（u,v）表示从顶点u到v有路径相连。我们以E所有边的集合，而边的权重则由权重函数w:E→[0,∞]定义。因此，w(u,v)就是从顶点u到顶点v的非负花费值（cost）。边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径（例如，最短路径）。这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。
1.算法描述
Dijkstra算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时，原点s的路径长度值被赋为0(d[s]=0)，同时把所有其他顶点的路径长度设为无穷大即表示我们不知道任何通向这些顶点的路径（对于V中所有顶点v除s外d[v]=∞）。当算法结束时，d[v]中储存的便是从s到v的最短路径，或者如果路径不存在的话则是无穷大。Dijkstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到v的最短路径可以通过将边（u,v）添加到尾部来拓展一条从s到u的路径。这条路径的长度是d[u]+w(u, v)。如果这个值比目前已知的d[v]的值要小，则可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d[u]达到它最终的值的时候每条边（u,v）都只被拓展一次。
算法维护两个顶点集S和Q。集合S保留了已知的所有d[v]的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d[u]值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。(https://www.daowen.com)
2.时间复杂度
可以用大O符号将该算法的运行时间表示为边数m和顶点数n的函数。Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q，所以搜索Q中最小元素的运算（Extract-Min(Q)）只需要线性搜索Q中的所有元素。这样的话算法的运行时间是O(n2)
对于边数少于n2的稀疏图来说，可以用邻接表更有效地实现该算法。同时需要将一个二叉堆或者斐波纳契堆用作优先队列来寻找最小的顶点（Extract-Min）。当用到二叉堆的时候，算法所需的时间为O((m+n)log n)，斐波纳契堆能稍微提高一些性能，让算法运行时间达到O(m+n log n)。然而，使用斐波纳契堆进行编程，常常会由于算法常数过大而导致速度没有显著提高。
3.相关问题及算法
原本Dijkstra算法还能够加以修改以扩充其功能。例如当面对一个问题时，有时我们可能希望取得数学上的次佳解。为了求得这些次佳解，先用原本的该算法求出最佳路径；接下来我们移除最佳路径中任一段路径，并对剩下来的子集合图再做一次最佳路径计算。对于最佳路径上的每一段路径做一样的操作，我们可以得到许多次佳路径解，将这些路径排序后即为原路径问题的次佳路径解集合。
开放最短路径优先（Open Shortest Path First，OSPF）算法是该算法在网络路由中的一个具体实现。与Dijkstra算法不同，Bellman-Ford算法可用于具有负花费边的图，只要图中不存在总花费为负值且从源点s可达的环路（如果有这样的环路，则最短路径不存在，因为沿环路循环多次即可无限制的降低总花费）。
与最短路径问题相关的一个著名问题是旅行商问题（Traveling Salesman Problem），此类问题要找出恰好通过所有目标点一次且最终回到原点的最短路径。然而该问题为“NP完全问题”。也就是说，与最短路径问题不同，旅行商问题不太可能具有多项式时间解法。如果有已知信息可用来估计某一点到目标点的距离，则可改用A*搜寻算法，以缩小最短路径的搜索范围。
