酷壳原文地址：http://coolshell.cn/articles/2322.html 本来是一篇老文章，最近翻出来一是作为一个程序员的编年史消遣一下；二是试图从其中找到业界这么多年来计算机文化的根，试图建立一点点与今年流行的互联网文化相关联的地方。 —————————————————————————————————————————————————— 原文如下： 了解过去，我

单源最短路径：给定带权有向图和源点v，求从v到G中其余各点的最短路径。 Dijkstra算法非常类似于最小生成树算法(的Prim)。 算法： 0、假设源为v0，设置辅助变量dist和pre，优先队列pq，按照dist[x]从小到达排序（小顶堆）。 1、如果v0->i连通，初始化dist[i]为w[v0][i]。放(dist[i], i)入pq。 2、循环，直到pq为空。 2.1、取出p