ACM选讲-最短路径 ACM选讲-最短路径 ■算法分析 构成的图形 算法分析 ■对于服务器i 设服务器的rank值为r 1)i自身感兴趣 2)如果R()>R)则不会对j感 3)如果R()≤RU)但是 i的最小距离 D>D(其中R()>R0)则R=3 R=1 录其中到的最小距离为D9 i不会对感兴趣 综上可以得到以下算法 R=n且到的距离<Di+1. 图论习题课 ACM选讲-最短路径 ACM选讲最小生成树 nsm=1,∥始时,它只对自己感兴趣 ACM 1251 题目描 (nc 1 in s(frank》】防每一个m口的节点 D[ll< Mn( Length(, srfranktll))/ R=rank. 茶若于条路 定的费用进行维护 现在决定却掉一些道 路,使得维护总费用 算法中最短距离用Djsa算法求得 最小,并且各村庄仍 然保持联通 ACM选讲-最小生成树 ACM选讲-关键路径 ■典型的最小生成树问题 定义:源点到汇点的最长路径叫关健路径 特点:只有加快关健路径上活动的完成时间才能加快工 前提:有向图必须无环 图论习题课 图论习题课6 图论习题课 ACM选讲-最短路径 „ 算法分析 „ 对于服务器i „ 1) i对自身感兴趣 „ 2）如果R(i)>R(j),则i不会对j感 兴趣. „ 3）如果R(i) ≤ R(j),但是 D(i,j)>D(i,k).其中 R(k)>R(j). 则 i不会对j感兴趣 „ 综上可以得到以下算法。 „ 构成的图形 1 2 3 4 30 20 20 R=2 R=1 R=3 R=1 图论习题课 ACM选讲-最短路径 „ 算法分析 „ 设服务器i的rank值为ri. „ 则B(i)= „ { „ R=10的服务器集合。记录其中到i的最小距离为D10 „ R=9 ，且到i的距离<D10.记录其中到i的最小距离为D9 „ …… „ R=ri,且到i的距离<Di+1. „ } 图论习题课 ACM选讲-最短路径 „ 算法分析 „ for (i=1..n) „ { int sum=1；//初始时，它只对自己感兴趣。 sum+=S(r[10]);//加入rank值等于10的服务器 for (rank=9..r[i]) { foreach (int j in S(r[rank]) ) //遍历每一个R=rank的节点 if( D[i][j] < Min ( Length (i , S(r[rank+1] ) ) ) // R=rank , { //且到i的距离<Drank+1 sum++; } } B[i]=sum; „ } „ 算法中最短距离用Dijkstra算法求得。 图论习题课 ACM选讲-最小生成树 „ ACM 1251 „ 题目描述： „ 若干村庄由若干条路 链接，每条路需要一 定的费用进行维护； 现在决定却掉一些道 路，使得维护总费用 最小，并且各村庄仍 然保持联通 图论习题课 ACM选讲-最小生成树 „ 典型的最小生成树问题 图论习题课 ACM选讲-关键路径 „ 定义：源点到汇点的最长路径叫关键路径 „ 特点：只有加快关键路径上活动的完成时间才能加快工 期。 „ 前提：有向图必须无环。 „ 例：求下图的关键路径