第四章第三节 最短路径算法 如下图所示，我们把边带有权值的图称为带权图。边的权值可以理解为两点之间的距离。一张图中任意两点间会有不同的路径相连。最短路径就是指连接两点的这些路径中最短的一条。我们有四种算法可以有效地解决最短路径问题。有一点需要读者特别注意：边的权值可以为负。当出现负边权时，有些算法不适用。一、求出最短路径的长度以下没有特别说明的话，disuv表示从u到v最短路径长度，wuv表示连接u，v的边的长度。1.Floyed-Warshall算法 O(N3) 简称Floyed(弗洛伊德)算法，是最简单的最短路径算法，可以计算图中任意两点间的最短路径。Floyed的时间复杂度是O (N3)，适用于出现负边权的情况。算法描述： 初始化：点u、v如果有边相连，则disuv=wuv。如果不相连则disuv=0 x7fffffffFor (k = 1; k = n; k+) For (i = 1; i = n; i+) For (j = 1; j disik + diskj) disij = disik + diskj; 算法结束：disij得出的就是从i到j的最短路径。算法分析&思想讲解：三层循环，第一层循环中间点k，第二第三层循环起点终点i、j，算法的思想很容易理解：如果点i到点k的距离加上点k到点j的距离小于原先点i到点j的距离，那么就用这个更短的路径长度来更新原先点i到点j的距离。在上图中，因为dis13+dis32dis12，所以就用dis13+dis32来更新原先1到2的距离。我们在初始化时，把不相连的点之间的距离设为一个很大的数，不妨可以看作这两点相隔很远很远，如果两者之间有最短路径的话，就会更新成最短路径的长度。Floyed算法的时间复杂度是O(N3)。 1 2 3 216Floyed算法变形：如果是一个没有边权的图，把相连的两点间的距离设为disij=true，不相连的两点设为disij=false，用Floyed算法的变形：For (k = 1; k = n; k+) For (i = 1; i = n; i+) For (j = 1; j = n; j+) disij = disij | (disik & diskj); 用这个办法可以判断一张图中的两点是否相连。最后再强调一点：用来循环中间点的变量k必须放在最外面一层循环。【例4-1】、最短路径问题【问题描述】平面上有n个点（n=100），每个点的坐标均在-1000010000之间。其中的一些点之间有连线。若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。【输入格式】 输入文件为short.in，共n+m+3行，其中: 第一行为整数n。 第2行到第n+1行（共n行） ，每行两个整数x和y，描述了一个点的坐标。 第n+2行为一个整数m，表示图中连线的个数。 此后的m 行，每行描述一条连线，由两个整数i和j组成，表示第i个点和第j个点之间有连线。 最后一行：两个整数s和t，分别表示源点和目标点。 【输出格式】 输出文件为short.out，仅一行，一个实数（保留两位小数），表示从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 5 【输出样例输出样例】3.41【参考程序】#include#include#include#includeusing namespace std;int a1013;double f101101;int n,i,j,k,x,y,m,s,e;int main() freopen(short.in,r,stdin); freopen(short.out,w,stdout); cin n; for (i = 1; i ai1 ai2; cin m; memset(f,0 x7f,sizeof(f); /初始化f数组为最大值 for (i = 1; i x y; fyx = fxy = sqrt(pow(double(ax1-ay1),2)+pow(double(ax2-ay2),2); /pow(x,y)表示xy，其中x,y必须为double类型，要用cmath库 cin s e; for (k = 1; k = n; k+) /floyed 最短路算法 for (i = 1; i = n; i+) for (j = 1; j = n; j+) if (i != j) & (i != k) & (j != k) & (fik+fkj fij) fij = fik + fkj; printf(%.2lfn,fse); return 0;【例例4-2】牛的旅行牛的旅行【问题描述问题描述】农民农民JohnJohn的农场里有很多牧区。有的路径连接一些特定的牧区。一的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言，你能看到至少有两片所有连通的牧区称为一个牧场。但是就目前而言，你能看到至少有两个牧区不连通。现在，个牧区不连通。现在，JohnJohn想在农场里添加一条路径想在农场里添加一条路径 ( ( 注意，恰好一条注意，恰好一条 ) )。对这条路径有这样的限制：一个牧场的直径就是牧场中最远的两个牧。对这条路径有这样的限制：一个牧场的直径就是牧场中最远的两个牧区的距离区的距离 ( ( 本题中所提到的所有距离指的都是最短的距离本题中所提到的所有距离指的都是最短的距离 ) )。考虑如下。考虑如下的两个牧场，图是有的两个牧场，图是有5 5个牧区的牧场，牧区用个牧区的牧场，牧区用“* *”表示，路径用直线表示，路径用直线表示。每一个牧区都有自己的坐标：表示。每一个牧区都有自己的坐标： 图所示的牧场的直径大约是图所示的牧场的直径大约是12.07106, 12.07106, 最远的两个牧区是最远的两个牧区是A A和和E E，它们之间的最短路径是，它们之间的最短路径是A-B-EA-B-E。 这两个牧场都在这两个牧场都在JohnJohn的农的农场上。场上。JohnJohn将会在两个牧场中各选一个牧区，然后用一条路径连起将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。注意，如果两来，使得连通后这个新的更大的牧场有最小的直径。注意，如果两条路径中途相交，我们不认为它们是连通的。只有两条路径在同一条路径中途相交，我们不认为它们是连通的。只有两条路径在同一个牧区相交，我们才认为它们是连通的。个牧区相交，我们才认为它们是连通的。 现在请你编程找出一现在请你编程找出一条连接两个不同牧场的路径，使得连上这条路径后，这个更大的新条连接两个不同牧场的路径，使得连上这条路径后，这个更大的新牧场有最小的直径。牧场有最小的直径。【输入格式输入格式】 第第 1 1 行：一个整数行：一个整数N (1 = N = N (1 = N = 150), 150), 表示牧区数；表示牧区数； 第第 2 2 到到 N+1 N+1 行：行：每行两个整数每行两个整数X X，Y ( 0 = XY ( 0 = X，Y= 100000 Y= 100000 ) )， 表示表示N N个牧区的坐标。每个牧区的坐标个牧区的坐标。每个牧区的坐标都是不一样的。都是不一样的。 第第 N+2 N+2 行到第行到第 2*N+1 2*N+1 行：每行包括行：每行包括N N个数字个数字 ( 0( 0或或1 ) 1 ) 表表示一个对称邻接矩阵。示一个对称邻接矩阵。 例如，题目描例如，题目描述中的两个牧场的矩阵描述如下：述中的两个牧场的矩阵描述如下： A B C D E F G H A B C D E F G H A 0 1 0 0 0 0 0 0 A 0 1 0 0 0 0 0 0 B 1 0 1 1 1 0 0 0 B 1 0 1 1 1 0 0 0 C 0 1 0 0 1 0 0 0 C 0 1 0 0 1 0 0 0 D 0 1 0 0 1 0 0 0 D 0 1 0 0 1 0 0 0 E 0 1 1 1 0 0 0 0 E 0 1 1 1 0 0 0 0 F 0 0 0 0 0 0 1 0 F 0 0 0 0 0 0 1 0 G 0 0 0 0 0 1 0 1 G 0 0 0 0 0 1 0 1 H 0 0 0 0 0 0 1 0 H 0 0 0 0 0 0 1 0 输入数据中至少包括两个不连通的牧区。输入数据中至少包括两个不连通的牧区。【输出格式输出格式】 只有一行，包括一个实数，表示所只有一行，包括一个实数，表示所求答案。数字保留六位小数。求答案。数字保留六位小数。【输入样例输入样例】 8 8 10 10 1010 15 1015 10 20 1020 10 15 15 1515 20 1520 15 30 1530 15 25 1025 10 30 1030 10 0100000001000000 1011100010111000 0100100001001000 0100100001001000 0111000001110000 0000001000000010 0000010100000101 0000001000000010【输出样例输出样例】 22.07106822.071068【算法分析】 用Floyed求出任两点间的最短路，然后求出每个点到所有可达的点的最大距离，记做mdisi。（Floyed算法） r1=max(mdisi) 然后枚举不连通的两点i,j，把他们连通，则新的直径是mdisi+mdisj+(i,j)间的距离。 r2=min(mdisi+mdisj+disi,j) re=max(r1,r2) re就是所求。【参考程序参考程序】#include#include #include#include using namespace std;using namespace std;double f151151,m151,minx,r,temp,x151,y151,maxint=1e12;double f151151,m151,minx,r,temp,x151,y151,maxint=1e12;double double dist(intdist(int i,inti,int j) j) return return sqrt(xi-xjsqrt(xi-xj)*()*(xi-xj)+(yi-yjxi-xj)+(yi-yj)*()*(yi-yjyi-yj) ; ) ; intint main() main() intint i,j,n,k;chari,j,n,k;char c; c; cincinn;n; for(ifor(i=1;i=1;ixixiyiyi; for(ifor(i=1;i=1;i=n;in;i+)+) for(jfor(j=1;j=1;jc;c; if(cif(c=1)fij=1)fij=dist(i,jdist(i,j);); else else fijfij=maxintmaxint; ; for(kfor(k=1;k=1;k=n;kn;k+)+) for(ifor(i=1;i=1;i=n;in;i+)+) for(jfor(j=1;j=1;j=n;jn;j+)+) if(iif(i!=!=j&ij&i!=!=k&jk&j!=k)!=k) if(fikif(fikmaxint-1&fkjmaxint-1)maxint-1&fkjfik+fkjfik+fkj) fijfij=fik+fkjfik+fkj; memset(m,0,sizeof(m);memset(m,0,sizeof(m); for(ifor(i=1;i=1;i=n;in;i+)+) for(jfor(j=1;j=1;j=n;jn;j+)+) if(fijif(fijmaxint-1&mimaxint-1&mifij)mifij)mi=fijfij; ; minx=