信息学奥赛一本通-第4章--第3-4节-图论算法(C++版).ppt

1、在第4章和第3节中，最短路径算法，如下图所示，我们把带加权边的图称为加权图。边的重量可以理解为两点之间的距离。图片中任何两点之间都会有不同的路径。最短路径是连接两点的最短路径。我们有四种算法可以有效地解决最短路径问题。读者应该特别注意的一点是，边缘的重量可能是负的。当出现负边缘权重时，一些算法不适用。1.寻找最短路径的长度除非下面另有说明，否则disuv表示从U到V的最短路径长度，wuv表示连接U和v1的边的长度。Floyed-Warshall算法O(N3)是最简单的最短路径算法，它可以计算图中任意两点之间的最短路径。Floyed的时间复杂度为O (N3)，适用于负边缘权重的情况。算法描述：初

2、始化：如果点u和v是由边连接的，则disuv=wuv。如果未连接，则disuv=0 x7fffffff For(k=1；k disik diskj)disij=disik diskj；算法结束：得出从I到j的最短路径。算法分析k=n；(I=1；i=n。(j=1；j=n。dissij=dissij | | (dissik可以判断图片中的两点是否以这种方式连接。最后，再强调一点：用于循环中间点的变量k必须放在最外面的循环中。示例4-1，最短路径问题问题描述平面上有n个点(n=100)，每个点的坐标在-100001000之间。有些点是相连的。如果有联系，就意味着它可以从一点到达另一点，也就是说，两点

3、之间有一条通道，通道的距离就是两点之间的直线距离。现在的任务是找到从一点到另一点的最短路径。输入格式输入文件很短，总共有n m 3行，其中：的第一行是整数n。第2行到第1行(总共n行)，每行有两个整数x和y，它们描述一个点的坐标。第n行是一个整数m，表示图中的连接数。下面的m条线，每条线描述一条连接线，由两个整数I和j组成，表示第I点和第j点之间有一条连接线。最后一行：两个整数，s和t，分别代表源点和目标点。输出格式输出文件很短，只有一行和一个实数(保留两位小数)，表示从s到T的最短路径长度.输入示例 5 0 0 2 0 2 2 0 2 3 1，5 1 2 1 3 1 4 2 5 3 5 1

4、5，输出示例 3.41，参考程序 # include # include # include使用命名空间STDint a1013双f101101int n，I，j，k，x，y，m，s，e；int main() freopen(short.in，r，stdin)；freopen(短路输出、w、stdout)。CINn；对于(I=1；i ai1 ai2CINm；memset(f，0 x7f，size of(f)；/将f数组初始化为最大值，对于(I=1；I x y；fyx=fxy=sqrt(功率(双(ax1-ay1)，2)功率(双(ax2-ay2)，2)；/power(x，y)代表xy，其中x，y必

5、须是双精度类型，应使用cmath库CIN s . e；对于(k=1；k=n；K) /floyed最短路径算法(I=1；i=n。I)对于(j=1；j=n。j)如果(I！=j)，示例4-2牛旅行问题描述农民约翰的农场有许多牧区。一些路径连接一些特定的牧区。一个有各种联系的牧区叫做牧场。但是现在，你可以看到至少有两个牧区是不相连的。现在，约翰想给农场增加一条路。这条道路有这样一个限制：牧场的直径是牧场中最远的两个牧区之间的距离(本主题中提到的所有距离都指最短距离)。考虑以下两个牧场。图为五个牧区的牧场，用“*”表示牧区，用直线表示路径。每个牧区都有自己的坐标：图中显示的牧区直径约为12.07106，

6、最远的两个牧区是A和E，它们之间的最短路径是A-B-E。两个牧场都在约翰的农场。约翰将在两个牧场中的每一个中选择一个牧区，然后用一条小路把它们连接起来，这样新的和更大的牧场在连接后将有最小的直径。请注意，如果两条路径相交一半，我们不认为它们是相连的。只有当两条路在同一个牧区相交时，我们才能认为它们是相连的。现在，请编程找到一条连接两个不同牧场的路径，这样在连接这条路径后，这个更大的新牧场将具有最小的直径。输入格式第1行：整数N (1=N=150)，表示牧区的数量；第2行到第1行：每行有两个整数X，Y (0=X，Y=100000)，代表N个牧区的坐标。每个牧区的坐标是不同的。第二行到第二行*第一

7、行：每一行包括代表对称邻接矩阵的N个数字(0或1)。例如，标题描述中的两个牧场的矩阵描述如下：a b c d e f g h a 0 1 000 000 b 1 01 1 000 c 0 1 00 00d 0 1 00 100 00 e 0 11 00 00 f 0 000 000 10g 0 000 001 01h 0 000 000 10输入数据包括至少两个未连接的牧区。output format只有一行，包括一个实数，表示所需的答案。数字保留六位小数。输入样本8 10 10 15 10 20 10 15 20 15 30 15 20 30 10 30 10 0100000 1011000

8、 01001000 0110000 01110000 00000000000000000000000000000000000000000000000000000000000000100000000000010000000000000000000000000000R2=最小(最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，最小，参考程序 #包含#包含使用命名空间标准；double f151151，m151，minx，r

9、，temp，x151，y151，maxint=1e12double dist(int i，int j)返回sqrt(Xi-XJ)*(Xi-XJ)(yi-yj)*(yi-yj)；int main() int i，j，n，k；char c；cinn对于(I=1；ixiyi对于(I=1；IC；if(c=1)fij=dist(i，j)；否则fij=最大值。对于(k=1；fkj=fkj；memset(m，0，sizeof(m)；对于(I=1；imaxint-1) temp=dist(i，j)；if(minxmi mj temp)minx=mi mj temp。r=0；对于(I=1；minx=miprin

10、tf(%.6lf，minx)；返回0；2.Dijkstra算法O (N2)是一种计算从一点到所有其他点的最短路径的算法，它是一种单源最短路径算法。也就是说，只能计算只有一个起点的情况。迪克斯特拉的时间复杂度是O (N2)，所以它不能处理负边缘权重。算法描述：让起点为S，disv代表从S到V的最短路径，prev是V的前一个节点，用于输出路径。a)初始化：disv=(vs)；diss=0；pres=0；(I=1；i=n。一)1 .在没有被访问过的点中找到一个顶点u，这样苏迪是最小的。2.u被标记为确定的最短路径3。对于顶点v，如果(苏迪wuv disv) disv=苏迪wuv的每个未确定的最短路径

11、与u相连；prev=u；c)算法结束：disv是从s到v的最短距离；Prev是v的前体节点，用于输出路径。算法分析int a1013双c101bool b101双f101101int n，I，j，k，x，y，m，s，e；双重minldouble maxx=1e30cin北部；对于(I=1；i ai1 ai2对于(I=1；I m；对于(I=1；I x y；fxy=fyx=sqrt(功率(双(ax1-ay1)，2)功率(双(ax2-ay2)，2)；CINse；对于(I=1；i=n。I)ci=FSI；memset(b，false，sizeof(b)；/dijkstra最短路径bs=truecs=0；

12、对于(I=1；I=n-1；I)minl=maxx；k=0；对于(j=1；j=n。/如果(！Bj)，示例4-4最低成本问题描述在N个人中，有些人可以在他们的银行账户之间转账。这些人之间转账的手续费不同。如果在这些人之间转账时，手续费需要从转账金额中扣除多少百分比，那么在转账后，A至少需要多少才能让B收到100元？在“输入格式”的第一行输入两个正整数n和m，分别代表可以相互转账的总人数和人数的对数。在以下m行中的每一行输入三个正整数x、y、z、y和z，这意味着在标记为x的人和标记为y的人之间相互转账时，需要扣除z%手续费(z100)。在最后一行输入两个正整数a和b。数据保证了甲和乙之间可以直接或间

13、接进行转移输出格式输出甲使乙到达所需的总成本至少为100元。精确到小数点后8位。输入样本3 3 1 2 1 2 3 1 3 1 3 3 3 3 3输出样本103.07153164数据标度 1=n=2000，参考程序#包括使用命名空间stddouble a20012001，dis2001=0，minnint n，m，I，j，k，x，y，f 2001=0；void init()cinnm；对于(I=1；ixy(i=1)的void dijkstra(int x );I min)k=j；minn=disjfk=1；如果(k=y)断开；对于(j=1；jdisj)disj=disk * akj；int main()init()；Dijkstra(x)；printf(%0.8lf，100/disy)；返回0；3.贝尔曼-福特算法O(NE)被称为福特(Ford)算法，也用于计算从一点到所