ACM选讲-最短路径 ACM选讲-最短路径φ 解题思路 先回顾 Dijkstra算法 ■1,初始化顶点0到其众n-1个顶点的距高 类似与最短路径问, 2,0入s集合 区别在于路径长度随时间动态改变。 3,for(i=1.n-1) 适当修改 Dijkstra算法 在不属于S的顶点中拉到跑高0最短的顶点,入5集合 修改由于的加入导到0距高减小的距高。记录踏径 图论习题课 图论习题课 修改 Dijkstra算法中涉及到计算距离的地方 本题中的距高:路径距高+等待时间 ACM选讲-最短路径 设a:(c1,r1,tb1,p1)b:(c2r2,t2t2) ACM 1206 关健求等待时间W(ab)= 题目描述 ic=c2)retu0;/款色相同 若千个服务器组成的无向连通图中,每个节点度数不超过 if(tbl!=tp2) Return r1+mintbl, tp2 定义两点间的距高D(j)为它们的最短路径长度。其中 if(tpll-tb2)return r1+tbl+mingtp1+tb2 D(i,i)=0. 定义R()服务器的服务能力1≤R()≤10 if(tpl!=tb2) Return r1+mintpl, tb2> es if(tbl=tp 2)return r1+tp1+mintbl+tp2) 定义B():服务器感兴趣的服务器集合 Retun无穷 其中服务暑感兴趣指的是 任盒k,如果D(Lk)≤D(L〗都有R(k)≤R() 对给定的图G,求Σ|B(i 图论习题课 ACM选讲-最短路径 ACM选讲-最短路径 ■构成的图形 R=2 R=1 ■B(2)={2 R=1 ■B(4)={1,2,34 m1430 3420 图论习题课 图论习题课5 图论习题课 ACM选讲-最短路径 „ 解题思路 „ 类似与最短路径问题， „ 区别在于路径长度随时间动态改变。 „ 适当修改Dijkstra算法。 图论习题课 ACM选讲-最短路径 „ 先回顾Dijkstra 算法： „ 1，初始化顶点0到其余n-1个顶点的距离。 „ 2，0入S集合 „ 3，for(i=1..n-1) „ { 在不属于S的顶点中找到距离0最短的顶点j，j加入S集合。 if(j是目标顶点) return. 修改由于j的加入导致到0距离减小的距离。记录路径。 „ } 图论习题课 ACM选讲 ACM 1158 „ 修改Dijkstra算法中涉及到计算距离的地方。 „ 本题中的距离： 路径距离+等待时间。 „ 设a:(c1,r1,tb1,tp1) b:(c2,r2,tb2,tp2) „ 关键求等待时间W(a,b)= „ { if(c1==c2) return 0; //颜色相同 if(r1 != r2) return min{r1, r2} if(c1=B,c2=P) if(tb1!=tp2) Return r1+min{tb1, tp2} else if(tp1!=tb2) return r1+tb1+ming{tp1+tb2} else if(tp1!=tb2) Return r1+min{tp1, tb2} eles if(tb1!=tp2) return r1+tp1+min{tb1+tp2} Return 无穷 „ } 图论习题课 ACM选讲-最短路径 „ ACM 1206 „ 题目描述 „ 若干个服务器组成的无向连通图中，每个节点度数不超过 10. „ 定义两点间的距离D(i,j)为它们的最短路径长度。其中 D(i,i)=0. „ 定义R(i): 服务器i的服务能力. 1≤R(i) ≤ 10 „ 定义B(i): 服务器i感兴趣的服务器集合。 „ 其中服务器i对j感兴趣指的是: „ 任意k，如果D(i,k) ≤ D(i,j),都有R(k) ≤ R(j). „ 对给定的图G，求∑|B(i)|? 图论习题课 ACM选讲-最短路径 „ 输入数据： „ 4 3 „ 2 „ 3 „ 1 „ 1 „ 1 4 30 „ 2 3 20 „ 3 4 20 „ 构成的图形 1 2 3 4 30 20 20 R=2 R=1 R=3 R=1 图论习题课 ACM选讲-最短路径 „ B(1)={1,2} „ B(2)={2} „ B(3)={1,2} „ B(4)={1,2,3,4} „ 故：∑|B(i)|=9 „ 构成的图形 1 2 3 4 30 20 20 R=2 R=1 R=3 R=1