nbhkdz.com冰点文库

高中信息竞赛-数据结构—最短路径

时间:2010-08-26


最短路径

最短路问题的类型
1.单目标最短路径问题:找出从每一顶点v到某指定顶点u 单目标最短路径问题:找出从每一顶点v到某指定顶点u 的一条最短路径。把图中的每条边反向, 的一条最短路径。把图中的每条边反向,我们就可以把这 一问题转化为单源最短路径问题。 一问题转化为单源最短路径问题。 2.单对顶点间的最短路径问题:对于某给定顶点u 2.单对顶

点间的最短路径问题:对于某给定顶点u和v,找 单对顶点间的最短路径问题 出从u 的一条最短路径。如果我们解决了源顶点为u 出从u到v的一条最短路径。如果我们解决了源顶点为u的 单源问题,则这一问题也就获得了解决。一般来讲, 单源问题,则这一问题也就获得了解决。一般来讲,目前 还未发现比最好的单源算法更快的方法。 还未发现比最好的单源算法更快的方法。 3.每对顶点间的最短路径问题 对于每对顶点u 3.每对顶点间的最短路径问题:对于每对顶点u和v,找出 每对顶点间的最短路径问题: 的最短路径。 从u到v的最短路径。

计算最短路的常用算法
floyd算法: floyd算法:在边权非负的有向图中计算每对顶点间的最短 算法 路径问题。该算法在图的传递闭包的基础上形成; 路径问题。该算法在图的传递闭包的基础上形成; Dijkstra算法: Dijkstra算法:在边权非负的有向图中计算单源最短路径问 算法 该算法建立在松弛技术基础之上; 题。该算法建立在松弛技术基础之上; Bellman-Ford算法 Bellman-Ford算法:能在更一般的情况下解决单源点最短 算法: 路径问题。所谓一般情况,指的是有向图的边权可以为负, 路径问题。所谓一般情况,指的是有向图的边权可以为负, 但不允许存在负权回路。 但不允许存在负权回路。该算法亦是建立在松弛技术基础 之上的; 之上的; SPFA算法:是一种很高效的求图的最短路径的算法, SPFA算法:是一种很高效的求图的最短路径的算法,正负 算法 权都可以,还能够判断负权回路问题。 权都可以,还能够判断负权回路问题。

计算单源最短路问题(Dijkstra算法) 计算单源最短路问题(Dijkstra算法) 算法
计算单源最短路的思维方向:每次延长最短路时选择权最小的边, 计算单源最短路的思维方向:每次延长最短路时选择权最小的边,并调整 最短路外每个结点至出发结点的路长 计算单源最短路的步骤:把图中所有结点分为两组, 计算单源最短路的步骤:把图中所有结点分为两组,每一个结点对应一个 距离值: 距离值: 第一组:包括已确定最短路径的结点,结点对应的距离值是由v0到此结 第一组:包括已确定最短路径的结点,结点对应的距离值是由v0到此结 点的最短路径长度; 点的最短路径长度; 第二组:包括尚未确定最短路径的结点, v0经由 第二组:包括尚未确定最短路径的结点,结点对应的距离值 是v0经由 第一组结点(中间结点)至此结点的最短路径长度; 第一组结点(中间结点)至此结点的最短路径长度; 我们按最短路径长度递增的顺序把第二组的结点加到第一组中去, 我们按最短路径长度递增的顺序把第二组的结点加到第一组中去,直至 v0可达的所有结点都包含于第一组。在这个过程中,总保持从v0到第一组各 v0可达的所有结点都包含于第一组 在这个过程中,总保持从v0到第一组各 可达的所有结点都包含于第一组。 结点的最短路径长度都不大于从v0至第二组任何结点的路径长度 至第二组任何结点的路径长度。 结点的最短路径长度都不大于从v0至第二组任何结点的路径长度。

w0i disti = ∞

(v0 , vi ) ∈ E (v0 , vi ) E

初始时v0进入第一组 v0的距离值为 初始时v0进入第一组,v0的距离值为0;第二组包含其它所有结 进入第一组, 的距离值为0 点,这些结点对应的距离值为v0到它的值即map[v0][vi] 这些结点对应的距离值为v0到它的值即 到它的值即map[v0][vi] 然后每次从第二组的结点中选一个其距离值为最小的结点vm加 然后每次从第二组的结点中选一个其距离值为最小的结点vm加 到第一组中。每往第一组加入一个结点vm, 到第一组中。每往第一组加入一个结点vm,就要对第二组的各结 点的距离值作一次修正( vi为第二组的结点 vm,vi) 为第二组的结点, 点的距离值作一次修正(设vi为第二组的结点, (vm,vi)为图中 的边): 的边): 若加进vm做中间结点使得 至vi的路径长度更短 若加进vm做中间结点使得v0至vi的路径长度更短(即vi的距离 做中间结点使得v0 的路径长度更短( vi的距离 >vm的距离值 的距离值+Wmi),则要修改vi的距离 vi的距离值 vm的 ),则要修改 的距离( 的距离值← 值>vm的距离值+Wmi),则要修改vi的距离(vi的距离值←vm的 距离值+Wmi)。 )。修改后再选距离值最小的一个结点加入到第一组 距离值+Wmi)。修改后再选距离值最小的一个结点加入到第一组 如此进行下去, 中,…。如此进行下去,直至第一组囊括图的所有结点或再无可 加入第一组的结点存在。显然, 加入第一组的结点存在。显然,这种从第二组的结点中选距离值 最小的结点扩展是一种贪心策略。 最小的结点扩展是一种贪心策略。

Dijkstra算法中心 Dijkstra算法中心—— 选择+ 标记+ 扩展 算法中心——
3

Dijkstra算法框架 Dijkstra算法框架
数据定义说明: 数据定义说明: const int maxint=0xfffffff; int map[][]; //存储图 //存储图 int dist[]; //存储到源点的最短路径长度 //存储到源点的最短路径长度 int path[]; //存储到源点的最短路径走法 //存储到源点的最短路径走法 bool vs[]; //标记该顶点是否已经计算 //标记该顶点是否已经计算 从文件中读入图的邻接矩阵g ①从文件中读入图的邻接矩阵g; for(i=1;i<=n;i++) for(j=1;j<=n;j++) cin>>map[i][j]; //读入数据 //读入数据 边集数组初始化; ②边集数组初始化; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(map[i][j]==0)map[i][j]=maxint; if( //把没有通路的点(map[i][j]==0)间的路径置为最大值 //把没有通路的点 把没有通路的点(map[i][j]==0)间的路径置为最大值 cin>>v;//读入源点 可默认源点为1) cin>>v;//读入源点(可默认源点为1) 读入源点(

Dijkstra算法框架 Dijkstra算法框架
③求出Dijkstra ; 求出Dijkstra void dijkstra() { int i,j,k,w; for(i=1;i<=n;i++)//初始化 for(i=1;i<=n;i++)//初始化,置初值 初始化, {dist[i]=map[v][i];path[i]=v;vs[i]=false;} dist[v]=0;//处理源点 dist[v]=0;//处理源点 path[v]=0;vs[v]=true;//标记访问 path[v]=0;vs[v]=true;//标记访问 for(i=1;i<=n-1;i++)//Dijkstra算法核心 for(i=1;i<=n-1;i++)//Dijkstra算法核心 { w=maxint; for(j=1;j<=n;j++) if(!vs[j]&&dist[j]<w)//找到最小点 if(!vs[j]&&dist[j]<w)//找到最小点,注意判断条件 找到最小点, {k=j;w=dist[j];}//保存当前最短点 {k=j;w=dist[j];}//保存当前最短点 vs[k]=true;//将最短点做标记 vs[k]=true;//将最短点做标记 for(j=1;j<=n;j++)//利用找到的点优化还没有访问的点 for(j=1;j<=n;j++)//利用找到的点优化还没有访问的点 if(!vs[j]&&(map[k][j]!=maxint)&&dist[k]+map[k][j]<dist[j]) {dist[j]:=dist[k]+map[k,j];//修正最短路径 {dist[j]:=dist[k]+map[k,j];//修正最短路径 path[j]:=k; //保存路径 //保存路径 } } } 输出; ④ 输出;

典型例题—最短路径问题1249 典型例题—最短路径问题1249
Description: 平面上有n个点( <=100),每个点的坐标均在-10000到10000之 ),每个点的坐标均在 平面上有n个点(n<=100),每个点的坐标均在-10000到10000之 其中的一些点之间有连线.若有连线, 间.其中的一些点之间有连线.若有连线,则表示可从一个点到达另一 个点,即两点间有通路,通路的距离为两点间的直线距离. 个点,即两点间有通路,通路的距离为两点间的直线距离.现在的任务 是找出从一点到另一点之间的最短路径. 是找出从一点到另一点之间的最短路径. Input: Input: n+m+3行 共n+m+3行 第一行为整数n 第一行为整数n. 行到第n 每行两个整数x 描述了一个点的坐标( 第2行到第n+行,每行两个整数x和y,描述了一个点的坐标(以一 个空格分开) 个空格分开) 行为一个整数m 表示图中连线的个数. 第n+2行为一个整数m,表示图中连线的个数. 以后的m 每行描述一条连线,由两个整数i 组成,表示第i 以后的m行,每行描述一条连线,由两个整数i和j组成,表示第i个点 和第j个点之间有连线. 和第j个点之间有连线. 最后一行;两个整数s 分别表示源点和目标点. 最后一行;两个整数s和t,分别表示源点和目标点. Output: 仅一行,一个实数(保留两位小数),表示从s ),表示从 仅一行,一个实数(保留两位小数),表示从s到t的最短路径长度

典型例题—最短路径问题1249 典型例题—最短路径问题1249
Sample Input 5 00 20 22 02 31 5 12 13 14 25 35 15 Sample Output:3.41

典型例题—最短路径问题1249 典型例题—最短路径问题1249
int main() { int i,j,m,num1,num2; cin>>n; for(i=1;i<=n;i++) for(j=1;j<=n;j++)map[i][j]=maxint; for(i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]); cin>>m; for(i=1;i<=m;i++) { scanf("%d%d",&num1,&num2); map[num1][num2]=map[num2][num1]=dist(num1,num2); } cin>>st>>ed; dijkstra(st); return 0; }

典型例题—最短路径问题1249 典型例题—最短路径问题1249
void dijkstra(int v) { double min; int i,j,k; for(i=1;i<=n;i++) {dis[i]=map[v][i];vis[i]=false;} dis[st]=0;vis[v]=true; for(i=1;i<=nfor(i=1;i<=n-1;i++) { min=maxint; for(j=1;j<=n;j++) if(!vis[j]&&dis[j]<min){k=j;min=dis[j];} vis[k]=true; for(j=1;j<=n;j++) if(!vis[j]&&(map[k][j]!=maxint)&&dis[j]>dis[k]+map[k][j]) dis[j]=dis[k]+map[k][j]; } printf("%0.2f",dis[ed]); }

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

Floy算法 Floy算法—多源最短路 算法—
任意一对顶点之间的最短路径 这个问题的解法有两种: 这个问题的解法有两种: 一一种算法:分别以图中的每个顶点为源点共调用 次 一一种算法:分别以图中的每个顶点为源点共调用n次 一种算法 Dijkstra算法 这种算法的时间复杂度为 算法,这种算法的时间复杂度为 算法 这种算法的时间复杂度为O(n3); ; 另一种算法: 算法,它的思路简单 另一种算法:Floyed算法 它的思路简单 但时间复杂度 算法 它的思路简单,但时间复杂度 仍然为O(n3),下面介绍 下面介绍Floyed算法。 算法。 仍然为 下面介绍 算法

Floyd 算法的基本思路是: 算法的基本思路是: 从图的带权邻接矩阵A=[a(i,j)]n× 开始,递归地进行n次更新, 从图的带权邻接矩阵A=[a(i,j)]n×n开始,递归地进行n次更新,即由 矩阵D(0)=A,按一个公式,构造出矩阵D(1);又用同样地公式由D(1)构 矩阵D(0)=A,按一个公式,构造出矩阵D(1);又用同样地公式由D(1)构 造出D(2);……;最后又用同样的公式由D(n-1)构造出矩阵 构造出矩阵D(n)。 造出D(2);……;最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵 D(n)的 D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度,称D(n)为图的 列元素便是i号顶点到j号顶点的最短路径长度, D(n)为图的 距离矩阵,同时还可引入一个后继节点矩阵path来记录两点间的最短路 距离矩阵,同时还可引入一个后继节点矩阵path来记录两点间的最短路 径。 递推公式为: 递推公式为: D(0)=A; D(0)=A; D(1)=[dij(1)]n×n,其中dij(1)=min{dij(0),di1(0)+d1j(0)}; (1)]n× 其中d (0)}; n× 其中d (1)}; D(2)=[dij(2)] n×n,其中dij(2)=min{dij(1),di2(1)+d2j(1)}; …… D(n)=[dij(n)]n×n,其中dij(n)=min{dij(n-1),di,n-1(n-1)+dn-1,j(n-1)}; (n)]n×n,其中 其中d (n(ni,n- (n采用循环迭代可以简便求出上述矩阵序列,具体算法如下: 采用循环迭代可以简便求出上述矩阵序列,具体算法如下: D(i,j):dij(k); D(i,j):dij(k); Path(i,j):对应于d(i,j)(k)的路径上 的后继点,最终的取值为i Path(i,j):对应于d(i,j)(k)的路径上i的后继点,最终的取值为i到j的最短 的路径上i 路径上i的后继点。 路径上i的后继点。

Floy算法 Floy算法—框架结构 算法—
数据定义说明: 数据定义说明: map[][];//存储图 存储图 dist[][];//dis[i,j]=k,i和j之间最短路径长度为 之间最短路径长度为K 和 之间最短路径长度为 下面给出Floyed算法算法框架 算法算法框架: 下面给出 算法算法框架 从文件中读入图的邻接矩阵map; ①从文件中读入图的邻接矩阵 ; for(i=1;i<=n;i++) 一种算法 for(j=1;j<=n;j++) cin>>map[i][j]);//读入数据 读入数据 数组初始化; ②数组初始化; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(map[i][j]==0)map[i][j]=maxint; //把没有通路的点 把没有通路的点(map[I,j]=0)间的路径置为最大 间的路径置为最大maxint 把没有通路的点 间的路径置为最大

Floy算法 Floy算法—框架结构 算法—
算法框架; ③Floyed算法框架; 算法框架 void floyd() { int i,j,k; for(i=1;i<=n;i++) //复抄数组 复抄数组 for(j=1;j<=n;j++) dist[i][j]=map[i][j]; 一种算法 for(k=1;k<=n;k++) //枚举中间点 枚举中间点 for(i=1;i<=n;i++) //枚举起点 枚举起点 for(j=1;j<=n;j++) //枚举终点 枚举终点 if((dist[i][k]!=maxint)&&(dist[k][j]!=maxint) &&(dist[i][k]+dist[k][j]<dist[i][j])) dist[i][j]=dist[i][k]+dist[k][j]; }

例题选讲—牛的旅行2092 例题选讲—牛的旅行2092
Description:农民John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所 :农民 的农场里有很多牧区。 的农场里有很多牧区 有的路径连接一些特定的牧区。 有连通的牧区称为一个牧场。但是就目前而言,你能看到至少有两个牧区不连通。 有连通的牧区称为一个牧场。但是就目前而言,你能看到至少有两个牧区不连通。现 在,John想在农场里添加一条路径 ( 注意,恰好一条 )。对这条路径有这样的限制: 想在农场里添加一条路径 注意, 。对这条路径有这样的限制: 一个牧场的直径就是牧场中最远的两个牧区的距离 ( 本题中所提到的所有距离指的都 是有5个牧区的牧场 牧区用“ ”表示, 个牧区的牧场, 是最短的距离 )。考虑如下的两个牧场,图1是有 个牧区的牧场,牧区用“*”表示, 。考虑如下的两个牧场, 路径用直线表示。每一个牧区都有自己的坐标: 路径用直线表示。每一个牧区都有自己的坐标:

图1所示的牧场的直径大约是12.07106, 最远的两个牧区是A和E,它们之间的最 所示的牧场的直径大约是 最远的两个牧区是 和 , 短路径是A-B-E。 短路径是 。 这两个牧场都在John的农场上。John将会在两个牧场中各选一个牧区,然后用 的农场上。 将会在两个牧场中各选一个牧区, 这两个牧场都在 的农场上 将会在两个牧场中各选一个牧区 一条路径连起来,使得连通后这个新的更大的牧场有最小的直径。注意, 一条路径连起来,使得连通后这个新的更大的牧场有最小的直径。注意,如果两条路 径中途相交,我们不认为它们是连通的。只有两条路径在同一个牧区相交, 径中途相交,我们不认为它们是连通的。只有两条路径在同一个牧区相交,我们才认 为它们是连通的。 为它们是连通的。 现在请你编程找出一条连接两个不同牧场的路径,使得连上这条路径后, 现在请你编程找出一条连接两个不同牧场的路径,使得连上这条路径后,这个更 大的新牧场有最小的直径。 大的新牧场有最小的直径。

例题选讲—牛的旅行2092 例题选讲—牛的旅行2092
求出任两点间的最短路, 【分析】:用Floyd求出任两点间的最短路,然后求出每个点到所有可达的 分析】 求出任两点间的最短路 点的最大距离,记做mdis[i]。( 。(Floyd算法) 算法) 点的最大距离,记做 。( 算法 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就是所求。 就是所求。 就是所求

核 心 代 码

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++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(f[i][k]<maxint-1&&f[k][j]<maxint-1&&f[i][j]>f[i][k]+f[k][j]) f[i][j]=f[i][k]+f[k][j]; 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; for(i=1;i<=n;i++) for(j=1;j<=n;j++) 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);

BellmanBellman-Ford算法—单源最短路 算法—
与dijkstra算法一样都是求单源最短路径的算法,不同的是,在Bellmandijkstra算法一样都是求单源最短路径的算法 不同的是, Bellman算法一样都是求单源最短路径的算法, Ford算法中 路径的权值可以为负数。 Ford算法中,路径的权值可以为负数。 设想从我们可以从图中找到一个 算法中, 环路(即从v出发,经过若干个点之后又回到v 环路(即从v出发,经过若干个点之后又回到v)且这个环路中所有路径 的权值之和为负。那么通过这个环路, 的权值之和为负。那么通过这个环路,环路中任意两点的最短路径就可 以无穷小下去。如果不处理这个负环路,程序就会永远运行下去。 以无穷小下去。如果不处理这个负环路,程序就会永远运行下去。 而 Bellman-Ford算法具有分辨这种负环路的能力 Bellman-Ford算法具有分辨这种负环路的能力。 算法具有分辨这种负环路的能力。 适用条件& 适用条件&范围 1.单源最短路径(从源点s到其它所有顶点v); 1.单源最短路径 从源点s到其它所有顶点v); 单源最短路径( 2.有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图); 2.有向图 无向图(无向图可以看作(u,v),(v,u)同属于边集 的有向图); 有向图& 同属于边集E 3.边权可正可负(如有负权回路输出错误提示); 3.边权可正可负 如有负权回路输出错误提示); 边权可正可负( 4.差分约束系统; 4.差分约束系统 差分约束系统;

BellmanBellman-Ford算法—单源最短路 算法—
实质上是:从源点到每一个顶点的最短路径最多经历n-1 实质上是:从源点到每一个顶点的最短路径最多经历n 条边,都能够求出最短路径长度。 条边,都能够求出最短路径长度。故该算法就是从经过一条 两条边…….不断的迭代下去, …….不断的迭代下去 边,两条边…….不断的迭代下去,若迭代过程中某一步开 始不再更新则结束,如果更新了n 次还在更新, 始不再更新则结束,如果更新了n-1次还在更新,则存在负权 回路。 回路。

图的最短路径长度
k 1 2 3 4 5 6 d [0] 0 0 0 0 0 0
k

d [1] 6 3 1 1 1 1

k

d [2] 5 3 3 3 3 3

k

d [3] 5 5 5 5 5 5

k

d [4] ∞ 5 2 0 0 0

k

d [5] ∞ 4 4 4 4 4

k

d [6] ∞ ∞ 7 5 3 3

k

核心代码
do times++; //记录边的个数 //记录边的个数 quit=true; //标记是否有更新 //标记是否有更新 for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(dist[i]+cost[i][j]<dist[j]) { dist[j]=dist[i]+cost[i][j]; //修改 //修改 quit=false; //有更新结点 //有更新结点 } while(quit&&times>=n);

【模拟试题】Easy sssp1666 模拟试题】
Description 输入数据给出一个有N(2 1,000)个节点 个节点, 输入数据给出一个有N(2 <= N <= 1,000)个节点,M(M <= 100,000) 条边的带权有向图. 条边的带权有向图. 要求你写一个程序, 判断这个有向图中是否存在负权回路. 要求你写一个程序, 判断这个有向图中是否存在负权回路. 如果从一 个点沿着某条路径出发, 又回到了自己, 而且所经过的边上的权和小于0, 个点沿着某条路径出发, 又回到了自己, 而且所经过的边上的权和小于0, 就说这条路是一个负权回路. 就说这条路是一个负权回路. 如果存在负权回路, 只输出一行如果存在负权回路, 只输出一行-1; 如果不存在负权回路, 再求出一个点S(1 N)到每个点的最短 如果不存在负权回路, 再求出一个点S(1 <= S <= N)到每个点的最短 路的长度. 约定: S到 的距离为0, 如果S与这个点不连通, 则输出NoPath. 路的长度. 约定: S到S的距离为0, 如果S与这个点不连通, 则输出NoPath.

核心代码
void bellman_ford(int s) { int i,j,k; bool change; for(i=1;i<=n;i++)dist[i]=a[s][i]; dist[s]=0; memset(vis,0,sizeof(vis)); k=0;change=false; while(!change||k>n) { k++; change=false; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if((dist[i]!=maxx)&&(a[i][j]!=maxx)) if(dist[i]+a[i][j]<dist[j]) {change=true; dist[j]=dist[i]+a[i][j]; vis[j]++; if(vis[j]>50){bj=if(vis[j]>50){bj=-1;return;} } } if(k==n+1){bj=if(k==n+1){bj=-1;return;} }

SPFA算法 SPFA算法
SPFA,是一种很高效的求图的最短路径的算法。 SPFA,是一种很高效的求图的最短路径的算法。 用dijkstra的话,途中存在负权环的话就会失效。而bellmandijkstra的话 途中存在负权环的话就会失效。 bellman的话, ford的效率又相对较低 ford的效率又相对较低。 的效率又相对较低。 spfa的思路是:维护一个队列,先将给出的源点放入队首, spfa的思路是:维护一个队列,先将给出的源点放入队首,对其 的思路是 每条边连接的点进行松弛操作。如果改变后的点没在队列里, 每条边连接的点进行松弛操作。如果改变后的点没在队列里,就 将改变后的点加入队列。然后将上一个点取出队列, 将改变后的点加入队列。然后将上一个点取出队列,直到队列为 空。 判断负权环时,只要发现某一个点的拓展次数超过总结点数-1 判断负权环时,只要发现某一个点的拓展次数超过总结点数的话,就说明存在负权环, 的话,就说明存在负权环,因为如果这个节点的最短距离不停地 减小并且拓展次数超过总结点数时, 减小并且拓展次数超过总结点数时,该节点肯定被某个节点松弛 两次或两次以上,说明存在一条到达他的权值为负的路径。 两次或两次以上,说明存在一条到达他的权值为负的路径。

核心代码
#include<iostream> using namespace std; int d[101],a[201],e[101][101],b[101][101],n,m,i,j; bool c[101]; void spfa(int v) { int i,j,cl,op,fa; cl=1;op=1;a[cl]=v;c[v]=true; for(i=1;i<=n;i++)d[i]=10000000; d[v]=0; while(op<=cl) { fa=a[op];c[fa]=false; for(i=1;i<=n;i++) { if((b[fa][i]!=0)&&(d[i]>d[fa]+b[fa][i])) { e[fa][i]++;e[i][fa]++; if(e[i][fa]>=nif(e[i][fa]>=n-1){cout<<"exist"<<endl;return;} d[i]=d[fa]+b[fa][i]; if(c[i]==false){cl++;a[cl]=i;c[i]=true;} } } int main() { cin>>n>>m; for(i=1;i<=n;i++) for(j=1;j<=n;j++)cin>>b[i][j]; spfa(m); for(i=1;i<=n;i++) {cout<<d[i]<<" ";cout<<endl;} return 0; }

op++;
} }

典型例题— 典型例题—AIM NETBAR1974
【问题背景】 问题背景】 绵阳中学以人数众多闻名。三个年级共有10000多人 多人, 绵阳中学以人数众多闻名。三个年级共有10000多人,学生多了附近的网吧 也多。 也多。 Mzoiers都热衷于 Mzoiers都热衷于Dota,可学校的机子配置相当差(评测服务器除外),根 都热衷于Dota,可学校的机子配置相当差(评测服务器除外), ),根 本不能玩,那就只有去网吧。星期天到星期五都是晚上10:20才下晚自习 才下晚自习, 本不能玩,那就只有去网吧。星期天到星期五都是晚上10:20才下晚自习,几 乎没时间玩。然而星期六下午放假是绝好的时间,但是学校人多啊, 乎没时间玩。然而星期六下午放假是绝好的时间,但是学校人多啊,一放学去 网吧的人就开始狂奔,竞争之激烈,抢到机子的难度非常之大。 网吧的人就开始狂奔,竞争之激烈,抢到机子的难度非常之大。往往在我们到 达网吧之前都坐满了。 达网吧之前都坐满了。 学校到网吧的路是错综复杂的, 学校到网吧的路是错综复杂的,以致于到一个自己想去的网吧都有非常多的路 线可以选择,而路线的长度又不相同,这样就决定了要花费的时间, 线可以选择,而路线的长度又不相同,这样就决定了要花费的时间,因此想要 尽快到达,选择一条最佳的路线是很有必要的。 尽快到达,选择一条最佳的路线是很有必要的。 问题描述】 【问题描述】 为了简化问题,我们把学校与周边的网吧看做图中的顶点,学校与网吧, 为了简化问题,我们把学校与周边的网吧看做图中的顶点,学校与网吧, 网吧与网吧之间的路线看做边,每个边都有一个权, 网吧与网吧之间的路线看做边,每个边都有一个权,表示我们走完这条路的时 由于放学人流量大,如果反向走会有危险,因此这是一个有向图。 间,由于放学人流量大,如果反向走会有危险,因此这是一个有向图。 我的学校在S 想要去的网吧在T 你的任务就是选择一条最佳路线, 我的学校在S点,想要去的网吧在T点。你的任务就是选择一条最佳路线, 使得从学校到目的地网吧的时间最短,你只需要输出最短到达时间即可。 使得从学校到目的地网吧的时间最短,你只需要输出最短到达时间即可。 Input 输入文件中共有M+2行数据 第一行两个整数N,M,表示点数和边数; 行数据, 输入文件中共有M+2行数据,第一行两个整数N,M,表示点数和边数; 然后M行每行3个正整数(u,v,t),表示有一条可由u 耗时为t的边; 然后M行每行3个正整数(u,v,t),表示有一条可由u到v耗时为t的边; 最后一行两个正整数S,T。 最后一行两个正整数S,T。

典型例题— 典型例题—AIM NETBAR1974
Output 输出文件只有一行,一个整数表示最短时间,如果S,T之间不存在通路则输 输出文件只有一行,一个整数表示最短时间,如果S,T之间不存在通路则输 Solution!”(双引号不输出 双引号不输出,"!"为西文标点 为西文标点) 出“No Solution!”(双引号不输出,"!"为西文标点)。 Sample Input 44 123 2 4 10 135 345 14 Sample Output 10 数据规模】 【数据规模】 对于30%的数据保证有 的数据保证有1<=N<=1000,1<=M<=1000; 对于30%的数据保证有1<=N<=1000,1<=M<=1000; 对于全部的数据保证有1 N<=10000,1<=M<=100000。 对于全部的数据保证有1 < N<=10000,1<=M<=100000。

数据输入
void init() { int i,x,y,d; cin>>n>>m; for(i=1;i<=m;i++) {scanf("%d%d%d",&x,&y,&d); a[x][0]++; f[x][0]++; a[x][a[x][0]]=y; f[x][f[x][0]]=d; } cin>>s>>t; memset(vis,0,sizeof(vis)); }

SPFA模块 SPFA模块
void spfa(int st) { int i,open,closed,c,x; for(i=1;i<=n;i++)dist[i]=0xfffffff; vis[st]=true;q[1]=st;open=1;closed=1; dist[st]=0; while(open<=closed) { x=q[open]; for(i=1;i<=a[x][0];i++) if(dist[a[x][i]]>dist[x]+f[x][i]) { dist[a[x][i]]=dist[x]+f[x][i]; if(!vis[a[x][i]]) { closed++; q[closed]=a[x][i]; vis[a[x][i]]=true; } } open++;vis[x]=false; } }

计算最短路的常用算法
floyd算法: O(n^3);中间点—起点— floyd算法: O(n^3);中间点—起点—终点 算法 Dijkstra算法:单源, Dijkstra算法:单源,正权 O(n^2) BFS;以点向往扩展 BFS; 算法 Bellman-Ford算法 负权环; Bellman-Ford算法:负权环; O(n^2) ~ O(n^3) ;边数扩展 算法: SPFA算法: SPFA算法:高效单源,负正均可, O(2E) ;以点来优化 单源,负正均可, 算法


数据结构_图的最短路径实现

数据结构实验课程名称 题目名称 学生学院 专业班级 学号 数据结构实验 图的最短路径实现 应用数学学院 信息计算 1 班 3114008104 陈辉腾 刘志煌 学生姓名 指导教师...

《数据结构课程设计》最短路径问题实验报告

数据结构课程设计》最短路径问题实验报告_电脑基础知识_IT/计算机_专业资料。...个元 素的一维数组来存储顶点信息(下标为 i 的元素存储顶点 Vi 的信息) 。 ...

数据结构--图的最短路径

数据结构--图的最短路径_计算机软件及应用_IT/计算机_专业资料。江西理工大学 ...信息学院 621 单独完成 一、 实验目的 1、 按照老师要求实现对图最短路径的...

数据结构最短路径课设报告

数据结构最短路径课设报告_计算机软件及应用_IT/计算机_专业资料。数据结构与...[MAXV]; //存放顶点信息 }MGraph; //图的邻接矩阵类型 //以下定义邻接表...

C语言版数据结构最短路径

C语言版数据结构最短路径_计算机软件及应用_IT/计算机_专业资料。二.最短路径 ...*最大顶点个数*/ /*用 32767 表示∞*/ /*顶点编号*/ /*顶点其他信息*/...

数据结构——最短路径和最小生成树

数据结构——最短路径和最小生成树 隐藏>> 最短路径: 最短路径: #include<...[j] = MAXCOST; } } /* 读取边信息 */ for (k = 0; k < n; k+...

数据结构实验报告最短路径

数据结构实验报告最短路径_IT/计算机_专业资料。HUNAN UNIVERSITY 课程实习报告 题 目: 最短路径 学生姓名: 学生学号: 专业班级: 指导老师: 完成日期: 一、需求...

数据结构课程设计说明书最短路径

分析: 1.此系统要完成对火车站点信息的储存、修改、删除、添加和查询最短路线,因为涉 及到最短路线问题,所以数据结构优先考虑采用图的邻接矩阵储存结构,站点和行车...

数据结构课程设计-Floyd算法求解最短路径

数据结构课程设计-Floyd算法求解最短路径_工学_高等教育_教育专区。数据结构课程...若 增加的顶点使得路径比原路径短,则用新路径代替原始路径,将顶点信息存储在 ...

数据结构实验报告 最短路径

数据结构实验报告 最短路径_工学_高等教育_教育专区。数据结构实验报告 最短路径实验报告 实验名称 最短路径 课程名称 | | 数据结构与算法实验 专业班级:信息安全...