ACM最短路问题.pptVIP

最短路问题简介 主讲:wangfangbob Email:wangfangbob@ 最短路问题 单源最短路 所有点对最短路 单位权值 非负权值 负权值 单源最短路径 SSSP问题 Single Source Shortest Path 求给定点到其他所有点的最短路径 与SSSP有关的算法有Dijkstra、Bellman-Ford（提高篇讲过）等 单源最短路 图论的一个经典问题也是基本问题:求两个点之间的最短路径. 目前没有专门针对这个问题的算法 必须通过求所有点到一个固定的点,即单源,的最短路,来解决这个问题. 经典算法:dijkstra算法(有向图) “松驰”操作 单源最短路算法都是基于“松驰”操作 什么是“松驰”操作: 有一条边从i指向j那么:松驰(relax)操作: If (d[j] d[i] + cost[i][j])  d[j] = d[i] + cost[i][j]; 数组d是表示所有点到源点的距离 其实就是更新操作 Dijkstra Dijkstra Edsger Wybe Dijkstra 这个Dijkstra，就是那个提出“goto有害论”的Dijkstra，就是那个提出信号量和PV原语，解决了有趣的“哲学家聚餐”问题的 Dijkstra，那个Dijkstra最短路径算法的创造者，第一个Algol 60编译器的设计者和实现者，THE操作系统的设计者和开发者，那个与D. E. Knuth并称为我们这个时代最伟大的计算机科学家的人。 在与癌症进行了多年的斗争之后，伟大的荷兰计算机科学家Edsger Wybe Dijkstra已经于2002年8月6日在荷兰Nuenen自己的家中与世长辞！终年72岁。 Dijkstra伪代码 int dijkstra(int s,int t) { 初始化S={空集} d[s] = 0; 其余d值为正无穷大 while (NOT t in S) { 取出不在S中的最小的d[i]; for (所有不在S中且与i相邻的点j) if (d[j] d[i] + cost[i][j]) d[j] = d[i] + cost[i][j]; ( “松弛”操作” ) S = S + {i}; //把i点添加到集合S里 } return d[t]; } 关于算法的说明 每次选取的j使d []最小，这样可以保证它的路径已经是最短路。因为如果经过某个未标记点p到达j会产生更短的路，那么到达j的最短路长度必然要加上一个更大的d [p]，矛盾 d [k]=min{d [k],d [j]+cost[j][k]}的作用是在标记j以后更新d数组（松弛操作） 关于算法的说明 每次循环会对1个点进行标记，所以n-1次循环后所有点都做标记，d[]的含义变成可以经过所有点的最短距离，就是我们要的最短距离 如果找到的d[]最小的一个是d[]=无穷大，则可以提前结束循环，未做标记的点都是不可到达的 Dijkstra只能针对正权 所有边权非负 单源最短路 反例:Dijkstra的本质是基于贪心的思想 Dijkstra演示 Dijkstra复杂度 复杂度分析: 最朴素的实现O(V^2) 堆实现O(ElogV) Floyd-warshell 求所有点对的最短路径 DP 设opt[i][j][k]表示从i到j的路径中，经过的点的编号不超过k的最短路。 边界条件opt[i][j][0] = dis[i][j] 转移方程: opt[i][j][k] = Min(opt[i][j][k-1] , opt[i][k][k-1] + opt[k][j][k-1]) (k 0 , 0 = i , j = n) 则opt[i][j][n]即为所求 for(k=0;kn;++k){ for(i=0;in;++i){ for(j=0;jn;++j){ if(cost[i][j]cost[i][k]+cost[k][j]){ cost[i][j]=cost[i][k]+cost[k][j] } } } } Floyd-warshell 算法时间复杂度为O(n^3) 原程序实际上是这个DP的一个精巧的实现，省略了最后一维数组 练习题目 Toj 2870 The K-th City 单纯的Dijkstra Toj 2878 Internet is Faulty 先Floyed再Dijkstra, 而且路径权值是用乘法 计算,可以直接把算法中的+变成*来解决,或者取对数,变成+计算亦可. * * 第七届(1972年)图灵奖得主 1 2 3 10 20 -15 4 1 *