ACM最短路径算法

1、最短路径算法,问题引入： 中二尚、菜鸡然和小水虎从哈尔滨出发去宁波参加第二届CCPC全国总决赛，但是因为没有直达的火车票，而且学校穷，不给报销飞机票。现在已知可以从任意车站中转，也知道任意两个车站之间的票价，聪明的你们能否算出他们能参加比赛的最小花费？ 求图中任意两点之间的最短路径。,最近公共祖先LCA,Dijkstra算法及其队列优化,Dijkstra算法及其队列优化,Dijkstra算法及其队列优化,Dijkstra算法及其队列优化,Dijkstra算法优化： 从算法过程和代码中我们可以知道，Dijkstra算法的时间浪费在了每次都要遍历所有点去寻找当前dist数组中的最小值，所以我们可以

2、很轻易地想出利用堆或优先队列的方式对算法进行优化。 优化后的Dijkstra算法时间复杂度为O（ElogV）,Bellman-Ford算法,Bellman-Ford算法中边权可正可负，并且可以判断图中是否存在负环，而Dijkstra算法无法处理边权为负数的情况。 第一，初始化所有点。 第二，进行循环，遍历所有的边，进行松弛计算。 第三，遍历图中所有的边edge（u，v），判断是否存在这样情况：d（v）d (u)+w(u,v) 有则返回false，表示途中存在从源点可达的权为负的回路。,Bellman-Ford算法,数组disti记录从源点s到顶点i的路径长度 初始化disti为无穷大，表示不可

3、达，dists=0 for(int i=1;inodenum;i+) for(int j=0;jedgenum;j+) RELAX(); for(int j=0;jedgenum;j+) 仍然可以RELAX则return false; return true; ,SPFA算法,SPFA算法是西南交通大学段凡丁于1994年发表的。 设立一个先进先出的 队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为

4、止。,SPFA算法,定理：只要最短路径存在，上述SPFA算法必定能求出最小值。证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值dv变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。,SPFA算法,SPFA 是这样判断负环的： 如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图） 期望的时间复杂度：O(ke)， 其中k为所有顶点进队的平均次数，可以证明k一般小

5、于等于2 但是SPFA在最坏情况下会退化成Bellman算法。最坏时间复杂度为O（VE）,SPFA算法,SPFA算法有两个优化算法 SLF 和 LLL： SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)dist(i)，则将j插入队首，否则插入队尾。SLF 可使速度提高15 20% 在实际的应用中SPFA的算法时间效率不是很稳定 ，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法。,SPFA算法,初始化同Bellman-Ford算法。 将源点入队，设立cnt数组记录每个点入队次数，设立vis数组记录该点是否在队列中。 当队列非

6、空时： 取出队首，visu = false; for i : 1-n RELAX(u,i)； 如果不在队列中，visi = true，cnti+，如果入队次数大于等于n，return false，入队。,BFS求单源最短路径,在我们学习图的基本算法BFS 和DFS的时候，其实那就是一个求解每一步的权重都为1的最短路，那么权重不为1的情况我，我们是否继续使用呢？ 采用邻接表或前向星进行图的存储 ， 则BFS的时间复杂度为：开始的初始化O(V)+BFS操作O(E) = O (V+E),BFS求单源最短路径,源点入队且当前总距离为0 While(队列非空) 取队首元素 并pop if(队首为终点) 返回总距离 点标记为访问过 遍历队首点相连的所有点 if(点没被