重定向;重新导向; 戴克斯特拉算法（），又称迪杰斯特拉算法、Dijkstra算法，是由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年发现的算法，并于3年后在期刊上发表。戴克斯特拉算法使用类似广度优先搜索的方法解决赋权图的单源最短路径问题。 该算法存在很多变体：戴克斯特拉的原始版本仅适用于找到两个顶点之间的最短路径，后来更常见的变体固定了一个顶点作为源结点然后找到该顶点到图中所有其它结点的最短路径，产生一个最短路径树。 该算法解决了图 formula_1上带权的单源最短路径问题:196–206。具体来说，戴克斯特拉算法设置了一顶点集合formula_2，在集合formula_2中所有的顶点与源点formula_4之间的最终最短路径权值均已确定。算法反复选择最短路径估计最小的点formula_5并将formula_6加入formula_2中。该算法常用于路由算法或者作为其他图算法的一个子模块。举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离，该演算法可以用来找到两个城市之间的最短路径。 应当注意，绝大多数的戴克斯特拉算法不能有效处理带有负权边的图。 戴克斯特拉算法在计算机科学的人工智能等领域也被称为均一开销搜索，并被认为是的一个特例。 描述. 戴克斯特拉算法通过保留目前为止所找到的每个顶点formula_8从formula_4到formula_10的最短路径来工作。初始时，原点formula_4的路径权重被赋为 0 （即原点的实际最短路径=0）。同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径。当算法结束时，formula_12 中储存的便是从formula_4到formula_10的最短路径，或者如果路径不存在的话是无穷大。 松弛操作是戴克斯特拉算法的基础操作：如果存在一条从formula_6到formula_10的边，那么从formula_4到formula_10的一条新路径是将边formula_19添加到从formula_4到formula_6的路径尾部来拓展一条从formula_4到formula_10的路径。这条路径的长度是formula_24。如果这个值比目前已知的formula_12的值要小，那么可以用这个值来替代当前formula_12中的值。松弛边的操作一直执行到所有的formula_12都代表从formula_4到formula_10的最短路径的长度值。 算法维护两个顶点集合formula_2和formula_31。集合formula_2保留所有已知实际最短路径值的顶点，而集合formula_31则保留其他所有顶点。集合formula_2初始状态为空，而后每一步都有一个顶点从formula_31移动到formula_2。这个被选择的顶点是formula_31中拥有最小的formula_38值的顶点。当一个顶点formula_6从formula_31中转移到了formula_2中，算法对formula_6的每条外接边formula_43进行松弛。 《算法导论》中给出了以下伪代码：该伪代码计算并保留图formula_44中原点formula_4到每一顶点formula_10的最短距离formula_12。其中，函数formula_48将顶点集合formula_31中有最小formula_38值的顶点formula_6从formula_31中删除并返回formula_6。 1 function Dijkstra(G, w, s) 2   INITIALIZE-SINGLE-SOURCE(G, s) //实际上的操作是将每个除原点外的顶点的formula_12置为无穷大，formula_55 3   formula_56 4   formula_57                 //formula_31是顶点formula_59的一个优先队列，以顶点的最短路径估计排序 5   while(formula_60) 6       do formula_61 //选取formula_6为formula_31中最短路径估计最小的顶点 7 formula_64 8 for each vertex v formula_65 9           do RELAX(u, v, w)       //松弛成功的结点会被加入到队列中 如果我们只对在formula_4和formula_67之间寻找一条最短路径的话，我们可以在第5或第6行添加条件如果满足formula_68的话终止程序。 在肯尼·罗森所著的《离散数学及其应用》中给出了如下的另一份伪代码： 1 procedure Dijkstra(G：边全为正权的图） 3    for formula_71 to n 4       formula_72 5    formula_73 6    formula_74 7    while formula_75 8    begin 9      formula_76不属于formula_2的formula_78最小的一个顶点 10        formula_79 11        for 所有不属于formula_2的顶点formula_10 12            if formula_82 then formula_83 时间复杂度. 我们可以用大O符号将该算法的运行时间表示为边数formula_85和顶点数formula_86的函数。 对于任何基于顶点集formula_31的实现，算法的运行时间是formula_88，其中formula_89和formula_90分别表示完成键的降序排列时间和从formula_31中提取最小键值的时间。 对于没有任何优化的戴克斯特拉算法，实际上等价于每次遍历了整个图的所有结点来找到Q中满足条件的元素（即寻找最小的顶点是formula_92的），此外实际上还需要遍历所有的边一遍，因此算法的复杂度是formula_93。 对于边数少于formula_94的稀疏图来说，可以用邻接表来更有效的实现该算法。 可以使用一个二叉堆或者斐波纳契堆用作优先队列来寻找最小的顶点（formula_95）以优化算法。当用到二叉堆的时候，算法所需的时间为formula_96，斐波纳契堆能提高一些性能，让算法运行时间达到formula_97。然而，使用斐波纳契堆进行编程，有时会由于算法常数过大而导致速度没有显著提高。 下面是一些戴克斯特拉算法经典实现的复杂度比较： 正确性证明. 戴克斯特拉本人在他的论文中给出了一份简单的证明。 《算法导论》使用循环不变式（数学归纳法）给出了如下的一份证明： 已知一带权图formula_98，其加权函数formula_99的值非负，源点为formula_4。对该图运行戴克斯特拉算法，对所有formula_101有formula_102。其中formula_38表示u点的最短路径估计，formula_104表示formula_4到formula_6点的最短路径。 证明：证明如下的循环不变式成立即可：在每次执行EXTRACT-MIN时，对每个顶点formula_107，有formula_102成立即可。由于上界性质，在formula_6加入了formula_2之后，一旦有formula_102，则在后面的每次循环中都不会改变这个性质。 初始化：第一次循环前，formula_112，因此循环不变式显然成立。 保持：实际上要证明每一轮循环中加入到formula_2中的结点满足formula_102。利用反证法，假设formula_6是第一个不满足此条件的结点，考虑循环开始前的状况，首先formula_6一定不等于formula_4，这是显然的。其次formula_4一定有到formula_6的路径，否则路径为无穷大。那么假设在formula_6进入时，有最短路径formula_121，假设该路径上存在两个点formula_122，formula_123。formula_124、formula_125，且x是y的前驱，路径formula_126可以分解为formula_127（此处formula_128表示经过formula_129这条路径，后同），其中路径formula_129和路径formula_131可以为空。由于formula_6是第一个不满足formula_102的，又因为formula_122是满足该条件的，而且formula_135一定已经被松弛过了，所以formula_123是满足该条件的。 现在只需要推出矛盾，即可证明u不存在：formula_123在formula_6之前出现，而且图中所有权值非负，因此有formula_139，所以：formula_140，但是由于formula_6和formula_123同时在formula_143中，因此formula_144，因此必有formula_145，也就证明了formula_6点不可能不满足该条件，上述假设为假，原命题得证。 终止：终止时，formula_147，由于formula_148，因此formula_149，因此对所有formula_101有formula_102。 起源与历史. 从鹿特丹到格罗宁根的最短路径是什么？实际上，这就是对于任意两座城市之间的最短路问题。解决这个问题实际上大概只花了我20分钟：一天早上，我和我的未婚妻在阿姆斯特丹购物，累了，我们便坐在咖啡馆的露台上喝咖啡，然后我就试了一下能否用一个算法解决最短路问题。正如我所说，这是一个20分钟的发现。不过实际上，我在3年后的1959年才把这个算法发表在论文上。即使现在来看这篇论文的可读性也非常高，这个算法之所以如此优雅，其中一个原因就是我没用笔纸就设计了它。后来我才知道，没用笔纸设计的优点之一是你不得不避免所有可避免的复杂问题。令我惊讶的是，这个算法最终成为我成名的基石之一。 戴克斯特拉1956年在荷兰数学和计算机科学研究学会担任程序员时为了展示新型计算机ARMAC的功能曾思考过最短路径问题的解法。他的目标是让不去实际计算的人也能理解这个问题和解决的方法，于是他在发现了这个算法之后在ARMAC上做了简单实验。1959年，他正式将此算法发表在期刊上，该算法也成为了戴克斯特拉成名的基石之一。 相关应用. 中需要计算最短路时常常要用到该算法，该算法在开放最短路径优先和中间系统到中间系统协议中的相关应用是其在网络路由中的典型实现。 戴克斯特拉算法及其改进算法应用广泛，尤其是在寻路、交通、规划中。 如果有已知信息可用来估计某一点到目标点的距离，则可改用A*搜寻算法，以减小最短路径的搜索范围，戴克斯特拉算法本身也可以看作是A*搜索算法的一个特例。 戴克斯特拉算法本身采用了与Prim算法类似的贪心策略。快速行进算法与戴克斯特拉算法同样有相似之处。 参考源程序. 以下是该算法使用堆优化的一个C++实现参考： using namespace std; // iPair ==> Integer Pair（整数对） typedef pair iPair; // 加边 void addEdge(vector > adj[], int u, int v, int wt) adj[u].push_back(make_pair(v, wt)); adj[v].push_back(make_pair(u, wt)); // 计算最短路 void shortestPath(vector > adj[], int V, int src)   // 关于stl中的优先队列如何实现，参考下方网址：   // http://geeksquiz.com/implement-min-heap-using-stl/ priority_queue , greater > pq;   // 距离置为正无穷大   vector dist(V, INF); vector visited(V, false);   // 插入源点，距离为0   pq.push(make_pair(0, src)); dist[src] = 0;   /* 循环直到优先队列为空 */ while (!pq.empty())       // 每次从优先队列中取出顶点事实上是这一轮最短路径权值确定的点       int u = pq.top().second; pq.pop(); if (visited[u]) { continue; visited[u] = true;       // 遍历所有边       for (auto x : adj[u])           // 得到顶点边号以及边权 int v = x.first; int weight = x.second;           //可以松弛           if (dist[v] > dist[u] + weight) // 松弛 dist[v] = dist[u] + weight; pq.push(make_pair(dist[v], v)); }   // 打印最短路   printf("Vertex Distance from Source\n"); for (int i = 0; i adj[V]; addEdge(adj, 0, 1, 4); addEdge(adj, 0, 7, 8); addEdge(adj, 1, 2, 8); addEdge(adj, 1, 7, 11); addEdge(adj, 2, 3, 7); addEdge(adj, 2, 8, 2); addEdge(adj, 2, 5, 4); addEdge(adj, 3, 4, 9); addEdge(adj, 3, 5, 14); addEdge(adj, 4, 5, 10); addEdge(adj, 5, 6, 2); addEdge(adj, 6, 7, 1); addEdge(adj, 6, 8, 6); addEdge(adj, 7, 8, 7); shortestPath(adj, V, 0); return 0; 以下是该算法Python的一个实现: import sys max = sys.maxsize vertices_number = 6 adjacency_matrix = [ [0, 1, 10, -1, -1, 2], [10, 0, 1, -1, -1, -1], [1, 10, 0, -1, -1, -1], [-1, -1, 2, 0, 1, 10], [-1, -1, -1, 10, 0, 1], [-1, -1, -1, 1, 10, 0]] start = [] dest = ["2", "5"] key = [] def init_keys(s: int): global key key = [ max ] * vertices_number key[s] = 0 def dijkstra(from_vertex, dest_vertex): fid = int(from_vertex) - 1 tid = int(dest_vertex) - 1 init_keys(fid) rel = [fid] min_vertex = fid while len(rel) 0 \ and key[i] > key[min_vertex] + adjacency_matrix[min_vertex][i]: key[i] = key[min_vertex] + adjacency_matrix[min_vertex][i] hop_path.update({i + 1: {"from": min_vertex + 1, "cost": adjacency_matrix[min_vertex][i]}}) if min_vertex not in rel: rel.append(min_vertex) min_vertex = tid for i in range(vertices_number): if i not in rel and key[i] {}".format(str(next_hop), cost ,path_str) path_str = "{} -({})-> {}".format(str(hop_path[next_hop]["from"]), hop_path[next_hop]["cost"], path_str) return key[tid], path_str def find_shortest_router(): for s in start: print("Forwarding Table for {}".format(s)) print("{:>10} {:>10} {}".format("To", "Cost", "Path")) for d in dest: c, n = dijkstra(s, d) print("{:>10} {:>10} {}".format(d, c, n)) def main(): for i in range(1, vertices_number + 1): if str(i) not in dest: start.append(str(i)) find_shortest_router() if __name__ == '__main__': main() 参考. 扩展阅读.