第四章 第三节 最短路径算法.

Presentation on theme: "第四章 第三节 最短路径算法."— Presentation transcript:

1 第四章 第三节 最短路径算法

2 如下图所示，我们把边带有权值的图称为带权图。边的权值可以理解为两点之间的距离。一张图中任意两点间会有不同的路径相连。最短路径就是指连接两点的这些路径中最短的一条。
　　我们有四种算法可以有效地解决最短路径问题。有一点需要读者特别注意：边的权值可以为负。当出现负边权时，有些算法不适用。

3 一、求出最短路径的长度 　　以下没有特别说明的话，dis[u][v]表示从u到v最短路径长度，w[u][v]表示连接u，v的边的长度。 1.Floyed-Warshall算法 O(N3) 　　简称Floyed(弗洛伊德)算法，是最简单的最短路径算法，可以计算图中任意两点间的最短路径。Floyed的时间复杂度是O (N3)，适用于出现负边权的情况。 算法描述： 初始化：点u、v如果有边相连，则dis[u][v]=w[u][v]。 　　如果不相连则dis[u][v]=0x7fffffff For (k = 1; k <= n; k++) For (i = 1; i <= n; i++) For (j = 1; j <= n; j++) If (dis[i][j] >dis[i][k] + dis[k][j]) dis[i][j] = dis[i][k] + dis[k][j]; 算法结束：dis[i][j]得出的就是从i到j的最短路径。 算法分析&思想讲解： 　　三层循环，第一层循环中间点k，第二第三层循环起点终点i、j，算法的思想很容易理解：如果点i到点k的距离加上点k到点j的距离小于原先点i到点j的距离，那么就用这个更短的路径长度来更新原先点i到点j的距离。 　　在上图中，因为dis[1][3]+dis[3][2]<dis[1][2]，所以就用dis[1][3]+dis[3][2]来更新原先1到2的距离。 　　我们在初始化时，把不相连的点之间的距离设为一个很大的数，不妨可以看作这两点相隔很远很远，如果两者之间有最短路径的话，就会更新成最短路径的长度。Floyed算法的时间复杂度是O(N3)。 1 2 3 6

4 用这个办法可以判断一张图中的两点是否相连。 最后再强调一点：用来循环中间点的变量k必须放在最外面一层循环。
Floyed算法变形： 　　如果是一个没有边权的图，把相连的两点间的距离设为dis[i][j]=true，不相连的两点设为dis[i][j]=false，用Floyed算法的变形： For (k = 1; k <= n; k++) For (i = 1; i <= n; i++) For (j = 1; j <= n; j++) 　　 dis[i][j] = dis[i][j] || (dis[i][k] && dis[k][j]); 用这个办法可以判断一张图中的两点是否相连。 　　最后再强调一点：用来循环中间点的变量k必须放在最外面一层循环。

5 【例4-1】、最短路径问题 【问题描述】 　　平面上有n个点（n<=100），每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。 　　若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的 　　任务是找出从一点到另一点之间的最短路径。 【输入格式】 　　输入文件为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

6 【参考程序】 #include<cstdio> #include<iostream>
#include<cmath> #include<cstring> using namespace std; int a[101][3]; double f[101][101]; 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 <= n; i++) cin >> a[i][1] >> a[i][2]; cin >> m; memset(f,0x7f,sizeof(f)); //初始化f数组为最大值

7 for (i = 1; i <= m; i++) //预处理出x、y间距离
{ cin >> x >> y; f[y][x] = f[x][y] = sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2)); //pow(x,y)表示x^y，其中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) && (f[i][k]+f[k][j] < f[i][j])) f[i][j] = f[i][k] + f[k][j]; printf("%.2lf\n",f[s][e]); return 0;

8 【例4-2】牛的旅行 【问题描述】 　　农民John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言，你能看到至少有两个牧区不连通。现在，John想在农场里添加一条路径 ( 注意，恰好一条 )。对这条路径有这样的限制：一个牧场的直径就是牧场中最远的两个牧区的距离 ( 本题中所提到的所有距离指的都是最短的距离 )。考虑如下的两个牧场，图１是有5个牧区的牧场，牧区用“*”表示，路径用直线表示。每一个牧区都有自己的坐标： 　　图１所示的牧场的直径大约是 , 最远的两个牧区是A和E，它们之间的最短路径是A-B-E。 　　这两个牧场都在John的农场上。John将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。注意，如果两条路径中途相交，我们不认为它们是连通的。只有两条路径在同一个牧区相交，我们才认为它们是连通的。 　　现在请你编程找出一条连接两个不同牧场的路径，使得连上这条路径后，这个更大的新牧场有最小的直径。

9 【输出格式】 　 只有一行，包括一个实数，表示所求答案。数字保留六位小数。 【输入样例】 　 8 　 　 　 　 　 　 　 　 　 　 　 　 　 　 【输出样例】 　 【输入格式】 　 第 1 行：一个整数N (1 <= N <= 150), 表示牧区数； 　 第 2 到 N+1 行：每行两个整数X，Y ( 0 <= X，Y<= )， 表示N个牧区的坐标。每个牧区的坐标都是不一样的。 　 第 N+2 行到第 2*N+1 行：每行包括N个数字 ( 0或1 ) 表示一个对称邻接矩阵。 　 例如，题目描述中的两个牧场的矩阵描述如下： 　　　　　　A B C D E F G H 　　　　　 A 　　　　　 B 　　　　　 C 　　　　　 D 　　　　　 E 　　　　　 F 　　　　　 G 　　　　　 H 　　 输入数据中至少包括两个不连通的牧区。

10 【算法分析】 　 用Floyed求出任两点间的最短路，然后求出每个点到所有可达的点的最大距离，记做mdis[i]。（Floyed算法） r1=max(mdis[i]) 　 然后枚举不连通的两点i,j，把他们连通，则新的直径是mdis[i]+mdis[j]+(i,j)间的距离。 　 r2=min(mdis[i]+mdis[j]+dis[i,j]) 　 re=max(r1,r2) 　 re就是所求。

11 【参考程序】 #include<iostream> #include<cmath>
using namespace std; double f[151][151],m[151],minx,r,temp,x[151],y[151],maxint=1e12; double dist(int i,int j) { return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])) ; } int main() { int i,j,n,k;char c; cin>>n; for(i=1;i<=n;i++)cin>>x[i]>>y[i]; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { cin>>c; if(c=='1')f[i][j]=dist(i,j); else f[i][j]=maxint; for(k=1;k<=n;k++) if(i!=j&&i!=k&&j!=k) if(f[i][k]<maxint-1&&f[k][j]<maxint-1) if(f[i][j]>f[i][k]+f[k][j]) f[i][j]=f[i][k]+f[k][j];

12 memset(m,0,sizeof(m)); for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(f[i][j]<maxint-1&&m[i]<f[i][j])m[i]=f[i][j]; minx=1e20; if(i!=j&&f[i][j]>maxint-1) {temp=dist(i,j); if(minx>m[i]+m[j]+temp)minx=m[i]+m[j]+temp; } r=0; for(i=1;i<=n;i++)if (m[i]>minx)minx=m[i]; printf("%.6lf",minx); return 0;

13 2.Dijkstra算法O (N2) 用来计算从一个点到其他所有点的最短路径的算法，是一种单源最短路径算法。也就是说，只能计算起点只有一个的情况。 Dijkstra的时间复杂度是O (N2)，它不能处理存在负边权的情况。 算法描述： 设起点为s，dis[v]表示从s到v的最短路径，pre[v]为v的前驱节点，用来输出路径。 a)初始化：dis[v]=∞(v≠s); dis[s]=0; pre[s]=0; b)For (i = 1; i <= n ; i++) 1.在没有被访问过的点中找一个顶点u使得dis[u]是最小的。 2.u标记为已确定最短路径 3.For 与u相连的每个未确定最短路径的顶点v if (dis[u]+w[u][v] < dis[v]) { dis[v] = dis[u] + w[u][v]; pre[v] = u; } c)算法结束：dis[v]为s到v的最短距离；pre[v]为v的前驱节点，用来输出路径。

14 算法分析&思想讲解： 从起点到一个点的最短路径一定会经过至少一个“中转点”（例如下图1到5的最短路径，中转点是2。特殊地，我们认为起点1也是一个“中转点”）。显而易见，如果我们想求出起点到一个点的最短路径，那我们必然要先求出中转点的最短路径（例如我们必须先求出点2 的最短路径后，才能求出从起点到5的最短路径）。 换句话说，如果起点1到某一点V0的最短路径要经过中转点Vi，那么中转点Vi一定是先于V0被确定了最短路径的点。 中转点 终点 最短路 1 2 1、2 3 1、2、3 4 5 1 2 3 4 5 7 6 求解顺序 我们把点分为两类，一类是已确定最短路径的点，称为“白点”，另一类是未确定最短路径的点，称为“蓝点”。如果我们要求出一个点的最短路径，就是把这个点由蓝点变为白点。从起点到蓝点的最短路径上的中转点在这个时刻只能是白点。 Dijkstra的算法思想，就是一开始将起点到起点的距离标记为0，而后进行n次循环，每次找出一个到起点距离dis[u]最短的点u，将它从蓝点变为白点。随后枚举所有的蓝点vi，如果以此白点为中转到达蓝点vi的路径dis[u]+w[u][vi]更短的话，这将它作为vi的“更短路径”dis[vi]（此时还不确定是不是vi的最短路径）。 就这样，我们每找到一个白点，就尝试着用它修改其他所有的蓝点。中转点先于终点变成白点，故每一个终点一定能够被它的最后一个中转点所修改，而求得最短路径。

15 第一轮循环找到dis[1]最小，将1变成白点。
让我们对以上这段枯燥的文字做一番模拟，加深理解。 算法开始时，作为起点的dis[1] = 0，其他的点dis[i] = 0x7fffffff。 1 2 3 4 5 7 6 第一轮循环找到dis[1]最小，将1变成白点。 对所有的蓝点做出修改，使得dis[2]=2,dis[3]=4,dis[4]=7。

16 第二轮循环找到dis[2]最小，将2变成白点。
这时dis[2]，dis[3]，dis[4]被它的最后一个中转点1修改为了最短路径。 1 2 3 4 5 7 6 第二轮循环找到dis[2]最小，将2变成白点。 对所有的蓝点做出修改，使得dis[3]=3,dis[5]=4。

17 第三轮循环找到dis[3]最小，将3变成白点。
这时dis[3]，dis[5]被它们的最后一个中转点2修改为了最短路径。 1 2 3 4 5 7 6 第三轮循环找到dis[3]最小，将3变成白点。 对所有的蓝点做出修改，使得dis[4]=4。发现以3为中转不能修改5，说明3不是5的最后一个中转点。

18 2 5 -4 1 6 3 4 这时dis[4]也被它的最后一个中转点3修改为了最短路径。
接下来的两轮循环将4、5也变成白点。N轮循环结束后，所有的点的最短路径即能求出。 Dijkstra无法处理边权为负的情况，例如右图这个例子。 2到3的边权值为-4，显然从起点1到3的最短路径是-2（1→2→3），但是dijskstra在第二轮循环开始时会找到当前dis[i]最小的点3，并标记它为白点。 这时的dis[3]=1，然而1却不是从起点到点3的最短路径。因为3已被标记为白点，最短路径值dis[3]不会再被修改了，所以我们在边权存在负数的情况下得到了错误的答案！

19 【例4-3】、最短路径问题(Dijkstra)
题目参见“Floyed算法”，但本题要求使用dijkstra算法解决。 #include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; int a[101][3]; double c[101]; bool b[101]; double f[101][101]; int n,i,j,k,x,y,m,s,e; double minl; double maxx = 1e30; int main() { cin >> n; for (i = 1; i <= n; i++) cin >> a[i][1] >> a[i][2]; for(j = 1; j <= n; j++) f[i][j] = maxx; //f数组初始化最大值 cin >> m; for (i = 1; i <= m; i++) //预处理x.y间距离f[x][y] cin >> x >> y; f[x][y] = f[y][x] = sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2)); }

20 cin >> s >> e;
for (i = 1; i <= n; i++) c[i] = f[s][i]; memset(b,false,sizeof(b)); //dijkstra 最短路 b[s] = true; c[s] = 0; for (i = 1; i <= n-1; i++) { minl = maxx; k = 0; for (j = 1; j <= n; j++) //查找可以更新的点 if ((! b[j]) && (c[j] < minl)) minl = c[j]; k = j; } if (k == 0) break; b[k] = true; for (j = 1; j <= n; j++) if (c[k] + f[k][j] < c[j]) c[j] = c[k] + f[k][j]; printf("%.2lf\n",c[e]); return 0;

21 【例4-4】最小花费 【问题描述】 在n个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问A最少需要多少钱使得转账后B收到100元。 【输入格式】 第一行输入两个正整数n,m，分别表示总人数和可以互相转账的人的对数。 以下m行每行输入三个正整数x,y,z，表示标号为x的人和标号为y的人之间互相转账需要扣除z%的手续费 (z<100)。 最后一行输入两个正整数A,B。数据保证A与B之间可以直接或间接地转账。 【输出格式】 输出A使得B到账100元最少需要的总费用。精确到小数点后8位。 【输入样例】 3 3 1 2 1 2 3 2 1 3 3 1 3 【输出样例】 【数据规模】 1<=n<=2000

22 【参考程序】 #include<iostream> using namespace std; double a[2001][2001],dis[2001]={0},minn; int n,m,i,j,k,x,y,f[2001]={0}; void init() { cin>>n>>m; for(i=1;i<=m;i++) {scanf("%d%d",&j,&k); scanf("%lf",&a[j][k]); a[j][k]=(100-a[j][k])/100; a[k][j]=a[j][k]; } cin>>x>>y; void dijkstra(int x) for(i=1;i<=n;i++)dis[i]=a[x][i]; dis[x]=1;f[x]=1; for(i=1;i<=n-1;i++) { minn=0; for(j=1;j<=n;j++) if(f[j]==0&&dis[j]>minn){k=j;minn=dis[j];} f[k]=1; if(k==y)break; if(f[j]==0&&dis[k]*a[k][j]>dis[j])dis[j]=dis[k]*a[k][j]; int main() init(); dijkstra(x); printf("%0.8lf",100/dis[y]); return 0;

23 3.Bellman-Ford算法O(NE) 简称Ford（福特）算法，同样是用来计算从一个点到其他所有点的最短路径的算法，也是一种单源最短路径算法。 能够处理存在负边权的情况，但无法处理存在负权回路的情况（下文会有详细说明）。 算法时间复杂度：O(NE)，N是顶点数，E是边数。 算法实现： 设s为起点，dis[v]即为s到v的最短距离，pre[v]为v前驱。w[j]是边j的长度，且j连接u、v。 初始化：dis[s]=0,dis[v]=∞（v≠s），pre[s]=0 For (i = 1; i <= n-1; i++) For (j = 1; j <= E; j++) //注意要枚举所有边，不能枚举点。 if (dis[u]+w[j]<dis[v]) 　 //u、v分别是这条边连接的两个点。 { dis[v] =dis[u] + w[j]; pre[v] = u; }

24 在上面这个简单的模拟中能看到白点的“蔓延”情况。
算法分析&思想讲解： Bellman-Ford算法的思想很简单。一开始认为起点是白点(dis[1]=0)，每一次都枚举所有的边，必然会有一些边，连接着白点和蓝点。因此每次都能用所有的白点去修改所有的蓝点，每次循环也必然会有至少一个蓝点变成白点。 在上面这个简单的模拟中能看到白点的“蔓延”情况。

25 虽然Bellman-Ford算法可以求出存在负边权情况下的最短路径，却无法解决存在负权回路的情况。
负权回路： 虽然Bellman-Ford算法可以求出存在负边权情况下的最短路径，却无法解决存在负权回路的情况。 负权回路是指边权之和为负数的一条回路，上图中②-④-⑤-③-②这条回路的边权之和为-3。在有负权回路的情况下，从1到6的最短路径是多少？答案是无穷小，因为我们可以绕这条负权回路走无数圈，每走一圈路径值就减去3，最终达到无穷小。 所以说存在负权回路的图无法求出最短路径，Bellman-Ford算法可以在有负权回路的情况下输出错误提示。 如果在Bellman-Ford算法的两重循环完成后，还是存在某条边使得：dis[u]+w<dis[v]，则存在负权回路： For每条边(u,v) If (dis[u]+w<dis[v]) return False 如果我们规定每条边只能走一次，在这个前提下可以求出负权回路的最短路径。这个问题就留待读者自己思考（提示：对Floyed做一点小处理）。

26 题目参见“Floyed算法”，要求采用Bellman-Ford算法。
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int main() { double a[101][3],dis[1001],w[1001],min1; int n,m,x,y,k,f[1001][3],s,t; bool b[101]; cin>>n; for (int i=1;i<=n;i++) scanf("%lf%lf",&a[i][1],&a[i][2]); cin>>m; for (int i=1;i<=m;i++) //初始化数组dis，f dis[i]=0x7fffffff/3; f[i][1] = f[i][2] = 0x7fffffff/3; }

27 for (int i=1;i<=m;i++)
{ scanf("%d%d",&x,&y); f[i][1]=x; f[i][2]=y; w[i]=sqrt(pow(a[x][1]-a[y][1],2)+pow(a[x][2]-a[y][2],2)); } cin>>s>>t; dis[s]=0; for (int i=1;i<=n;i++) //算法主体 for (int j=1;j<=m;j++) if (dis[f[j][1]]+w[j]<dis[f[j][2]]) dis[f[j][2]]=dis[f[j][1]]+w[j]; if (dis[f[j][2]]+w[j]<dis[f[j][1]]) dis[f[j][1]]=dis[f[j][2]]+w[j]; printf("%.2f",dis[t]);

28 4、SPFA算法O(kE) SPFA是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。 主要思想是： 初始时将起点加入队列。每次从队列中取出一个元素，并对所有与它相邻的点进行修改，若某个相邻的点修改成功，则将其入队。直到队列为空时算法结束。 这个算法，简单的说就是队列优化的bellman-ford，利用了每个点不会更新次数太多的特点发明的此算法。 SPFA 在形式上和广度优先搜索非常类似，不同的是广度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是说一个点修改过其它的点之后，过了一段时间可能会获得更短的路径，于是再次用来修改其它的点，这样反复进行下去。 算法时间复杂度：O(kE)，E是边数。K是常数，平均值为2。 算法实现： dis[i]记录从起点s到i的最短路径，w[i][j]记录连接i，j的边的长度。pre[v]记录前趋。 team[1..n]为队列，头指针head，尾指针tail。 布尔数组exist[1..n]记录一个点是否现在存在在队列中。 初始化：dis[s]=0,dis[v]=∞（v≠s），memset(exist,false,sizeof(exist)); 起点入队team[1]=s; head=0; tail=1;exist[s]=true; do { 1、头指针向下移一位，取出指向的点u。 2、exist[u]=false;已被取出了队列 3、for与u相连的所有点v //注意不要去枚举所有点，用数组模拟邻接表存储 if (dis[v]>dis[u]+w[u][v]) dis[v]=dis[u]+w[u][v]; pre[v]=u; if (!exist[v]) //队列中不存在v点，v入队。 //尾指针下移一位，v入队; exist[v]=true; } ｝ while (head < tail); 循环队列： 　　采用循环队列能够降低队列大小，队列长度只需开到2*n+5即可。例题中的参考程序使用了循环队列。

29 【例4-6】、香甜的黄油(Sweet Butter)
【问题描述】 农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。 农夫John很狡猾。像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。 农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。 【输入格式】butter.in 第一行: 三个数：奶牛数N，牧场数P（2<=P<=800），牧场间道路数C(1<=C<=1450)。 第二行到第N+1行: 1到N头奶牛所在的牧场号。 第N+2行到第N+C+1行：每行有三个数：相连的牧场A、B，两牧场间距（1<=D<=255），当然，连接是双向的。 【输出格式】butter.out 一行 输出奶牛必须行走的最小的距离和. 【输入样例】 3 4 5 2 3 4 1 2 1 1 3 5 2 3 7 2 4 3 样例图形 P2 P1 C1 \ |\ \ | \ \ | \ \| \ C3 C2 P3 P4 【输出样例】 //说明：放在4号牧场最优

30 【参考程序】 #include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,p,c,i,j,x,y,t,min1,head,tail,tot,u; int a[801][801],b[501],dis[801],num[801],w[801][801],team[1601]; bool exist[801]; int main() { freopen("butter.in","r",stdin); freopen("butter.out","w",stdout); cin>>n>>p>>c; for(i=1;i<=p;i++) b[i]=0; num[i]=0; for(j=1;j<=p;j++) w[i][j]=0x7fffffff/3; } for(i=1;i<=n;i++) cin>>b[i]; for(i=1;i<=c;i++) //邻接矩阵存储 cin>>x>>y>>t; w[x][y]=t; a[x][++num[x]]=y; a[y][++num[y]]=x; w[y][x]=w[x][y];

31 min1=0x7fffffff/3; for(i=1;i<=p;i++) { for(j=1;j<=p;j++) dis[j]=0x7fffffff/3; memset(team,0,sizeof(team)); //队列数组初始化 memset(exist,false,sizeof(exist)); //exist标志初始化 dis[i]=0;team[1]=i;head=0;tail=1;exist[i]=true; //起始点入队 do head++; head=((head-1)%1601)+1; //循环队列处理 u=team[head]; exist[u]=false; for(j=1;j<=num[u];j++) if (dis[a[u][j]]>dis[u]+w[u][a[u][j]]) dis[a[u][j]]=dis[u]+w[u][a[u][j]]; if (!exist[a[u][j]]) tail++; tail=((tail-1)%1601)+1; team[tail]=a[u][j]; exist[a[u][j]]=true; } }while(head!=tail); tot=0; for(j=1;j<=n;j++) tot+=dis[b[j]]; if (tot<min1) min1=tot; cout<<min1; return 0;

32 二、输出最短路径 1.单源最短路径的输出 Dijkstra，Bellman-Ford，SPFA都是单源最短路径算法，它们的共同点是都有一个数组pre[x] 用来记录从起点到x的最短路径中，x的前驱结点是哪个。每次更新，我们就给pre[x]赋一个新值，结合上面的思想讲解，相信对于记录某点的前驱结点是不难理解的。那么怎么利用pre[x]数组输出最短路径方案呢？ 【例4-7】、最短路径问题(输出路径) 要求改写程序，用Dijkstra、Bellman-Ford、SPFA算法输出最短路径的方案。 使用一个小小的递归过程就能解决这一问题。 void print(int x) { if (pre[a][x] == 0) return; //起点的前驱我们已设为0 print(pre[a][x]); cout << "->" << x; } //主程序中： main ……（进行Dijkstra或Bellman-Ford，SPFA运算） cout << s; print(e); //s是起点，e是终点 2.Floyed算法输出最短路径 Floyed算法输出路径也是采用记录前驱点的方式。因为floyed是计算任意两点间最短路径的算法，dis[i][j]记录从i到j的最短路径值。故而我们定义pre[i][j]为一个二维数组，记录从i到j的最短路径中，j的前驱点是哪一个。

33 【例4-8】、最短路径问题(Floyed法输出路径)
要求改写Floyed的程序，模仿Dijkstra输出路径的方法用floyed输出最短路径方案。 【参考程序】 #include<iostream> #include<cmath> #include<cstring> using namespace std; double dis[101][101]; int x[101],y[101]; int pre[101][101]; int n,i,j,k,m,a,b; int pf(int x) { return x*x; } void print(int x) if (pre[a][x] == 0) return; //pre[a][a]=0,说明已经递归到起点a print(pre[a][x]); cout << "->" << x;

34 int main() { cin >> n; for (i = 1; i <= n; i++) cin >> x[i] >> y[i]; memset(dis,0x7f,sizeof(dis)); //初始化数组 cin >> m; memset(pre,0,sizeof(pre)); //初始化前驱数组 for (i = 1; i <= m; i++) cin >> a >> b; dis[a][b] = dis[b][a] = sqrt(pf(x[a]-x[b])+pf(y[a]-y[b])); pre[a][b] = a; //a与b相连，自然从a到b的最短路径b的前驱是a pre[b][a] = b; } for (k = 1; k <= n; k++) //floyed 最短路 for (j = 1; j <= n; j++) if ((i != j) && (i != k) && (j != k)) if (dis[i][j] > dis[i][k]+dis[k][j]) dis[i][j] = dis[i][k] + dis[k][j]; pre[i][j] = pre[k][j]; //从i到j的最短路径更新为i→k→j，那么i到j最短路径j的前驱就肯定与k到j最短路径j的前驱相同。 cout << a; print(b); //a是起点，b是终点 return 0; 最后再稍微提一提有向图求最短路径的方法：对有向图求最短路径上面的算法可以直接使用，只需注意如果从i到j只有一条有向边，w[i][j]赋值为这条边的权值，而将w[j][i]赋值为无穷大即可。

35 【上机练习】 1、信使 【问题描述】 战争时期，前线有n个哨所，每个哨所可能会与其他若干个哨所之间有通信联系。信使负责在哨所之间传递信息，当然，这是要花费一定时间的（以天为单位）。指挥部设在第一个哨所。当指挥部下达一个命令后，指挥部就派出若干个信使向与指挥部相连的哨所送信。当一个哨所接到信后，这个哨所内的信使们也以同样的方式向其他哨所送信。直至所有n个哨所全部接到命令后，送信才算成功。因为准备充足，每个哨所内都安排了足够的信使（如果一个哨所与其他k个哨所有通信联系的话，这个哨所内至少会配备k个信使）。 现在总指挥请你编一个程序，计算出完成整个送信过程最短需要多少时间。 【输入格式】 输入文件msner.in，第1行有两个整数n和m，中间用1个空格隔开，分别表示有n个哨所和m条通信线路。1<=n<=100。 第2至m+1行：每行三个整数i、j、k，中间用1个空格隔开，表示第i个和第j个哨所之间存在通信线路，且这条线路要花费k天。 【输出格式】 输出文件msner.out，仅一个整数，表示完成整个送信过程的最短时间。如果不是所有的哨所都能收到信，就输出-1。

36 【输入样例】 4 4 1 2 4 2 3 7 2 4 1 3 4 6 【输出样例】 11

37 2、最优乘车 【问题描述】 H城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴上线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。 一名旅客最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士, 这样换乘几次后到达S公园。 现在用整数1,2,…N 给H城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为1，S公园巴士站的编号为N。 写一个程序，帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到S公园的过程 中换车的次数最少。 【输入格式】 输入文件是Travel.in。文件的第一行有两个数字M和N(1<=M<=100 1<N<=500），表示开通了M条单程巴士线路，总共有N个车站。从第二行到第M刊行依次给出了第1条到第M条巴士线路的信息。其中第i+1行给出的是第i条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号相邻两个站号之间用一个空格隔开。 【输出格式】 输出文件是Travel.out，文件只有一行。如果无法乘巴士从饭店到达S公园，则输出"NO"，否则输出你的程序所找到的最少换车次数，换车次数为0表示不需换车即可到达。 【输入样例】Travel.in 3 7 6 7 【输出样例】Travel.out 2

38 3、最短路径 【问题描述】 给出一个有向图G=(V, E)，和一个源点v0∈V，请写一个程序输出v0和图G中其它顶点的最短路径。只要所有的有向环都是正的，我们就允许图的边有负值。顶点的标号从1到n（n为图G的顶点数）。 【输入格式】 第1行：一个正数n（2<=n<=80），表示图G的顶点总数。 第2行：一个整数，表示源点v0（v0∈V，v0可以是图G中任意一个顶点）。 第3至第n+2行，用一个邻接矩阵W给出了这个图。 【输出格式】 共包含n-1行，按照顶点编号从小到大的顺序，每行输出源点v0到一个顶点的最短距离。每行的具体格式参照样例。 【输入样例】 5 1 【输出样例】 (1 -> 2) = 2 (1 -> 3) = 5 (1 -> 4) = 9 (1 -> 5) = 9 样例所对应的图如下:

39 第四节 图的连通性问题 一、判断图中的两点是否连通 1、Floyed算法 时间复杂度：O(N3 ) 算法实现：
　　把相连的两点间的距离设为dis[i][j]=true,不相连的两点设为dis[i][j]=false，用Floyed算法的变形： 　for (k = 1; k <= n; k++) for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) 　 dis[i][j] = dis[i][j] || (dis[i][k] && dis[k][j]); 　　最后如果dis[i][j]=true的话，那么就说明两点之间有路径连通。 　　有向图与无向图都适用。

40 2、遍历算法 　　时间复杂度：O(N2 ) 算法实现： 　　从任意一个顶点出发，进行一次遍历，能够从这个点出发到达的点就与起点是联通的。这样就可以求出此顶点和其它各个顶点的连通情况。所以只要把每个顶点作为出发点都进行一次遍历，就能知道任意两个顶点之间是否有路存在。 　　可以使用DFS实现。 　　有向图与无向图都适用。

41 二、最小环问题 　　最小环就是指在一张图中找出一个环，使得这个环上的各条边的权值之和最小。在Floyed的同时，可以顺便算出最小环。 　　记两点间的最短路为dis[i][j]，g[i][j]为边<i,j>的权值。 　　for (k = 1; k <= n; k++) 　　　　{ 　　　 for (i = 1; i <= k-1; i++) for (j = i+1; j <= k-1; j++) 　　　　 answer = min(answer,dis[i][j]+g[j][k]+g[k][i]); 　　　 for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) 　　　　　 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); } 　　answer即为这张图的最小环。 　　一个环中的最大结点为k(编号最大)，与它相连的两个点为i,j，这个环的最短长度为g[i][k]+g[k][j]+(i到j的路径中,所有结点编号都小于k的最短路径长度)。 　　根据Floyed的原理，在最外层循环做了k-1次之后，dis[i][j]则代表了i到j的路径中，所有结点编号都小于k的最短路径。 　　综上所述，该算法一定能找到图中最小环。

42 三、求有向图的强连通分量 Kosaraju算法可以求出有向图中的强连通分量个数，并且对分属于不同强连通分量的点进行标记。它的算法描述较为简单： (1) 第一次对图G进行DFS遍历，并在遍历过程中，记录每一个点的退出顺序。以下图为例： 如果以1为起点遍历，访问结点的顺序如下： 结点第二次被访问即为退出之时，那么我们可以得到结点的退出顺序：

43 (2)倒转每一条边的方向，构造出一个反图G’。然后按照退出顺序的逆序对反图进行第二次DFS遍历。我们按1、4、2、3、5的逆序第二次DFS遍历：
访问过程如下： 每次遍历得到的那些点即属于同一个强连通分量。1、4属于同一个强连通分量，2、3、5属于另一个强连通分量。

44 【上机练习】 1、刻录光盘 【问题描述】 　　在FJOI2010夏令营快要结束的时候，很多营员提出来要把整个夏令营期间的资料刻录成一张光盘给大家，以便大家回去后继续学习。组委会觉得这个主意不错！可是组委会一时没有足够的空光盘，没法保证每个人都能拿到刻录上资料的光盘，怎么办呢？！ 　　DYJ分析了一下所有营员的地域关系，发现有些营员是一个城市的，其实他们只需要一张就可以了，因为一个人拿到光盘后，其他人可以带着U盘之类的东西去拷贝啊！ 　　他们愿意某一些人到他那儿拷贝资料，当然也可能不愿意让另外一些人到他那儿拷贝资料，这与我们FJOI宣扬的团队合作精神格格不入！！！ 　　现在假设总共有N个营员（2<=N<=200），每个营员的编号为1~N。DYJ给每个人发了一张调查表，让每个营员填上自己愿意让哪些人到他那儿拷贝资料。当然，如果A愿意把资料拷贝给B，而B又愿意把资料拷贝给C，则一旦A获得了资料，则B，C都会获得资料。 　　现在，请你编写一个程序，根据回收上来的调查表，帮助DYJ计算出组委会至少要刻录多少张光盘，才能保证所有营员回去后都能得到夏令营资料？

45 【输入样例】 【输出样例】 5 2 4 3 0 4 5 0 1 0 1 【输入格式】cdrom.in
先是一个数N，接下来的N行，分别表示各个营员愿意把自己获得的资料拷贝给其他哪些营员。即输入数据的第i+1行表示第i个营员愿意把资料拷贝给那些营员的编号，以一个0结束。如果一个营员不愿意拷贝资料给任何人，则相应的行只有1个0，一行中的若干数之间用一个空格隔开。 【输出格式】cdrom.out 一个正整数，表示最少要刻录的光盘数。 【输入样例】 【输出样例】 5 4 5 0 1 0 1