最短路（算法思想例题代码）

最短路

最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短，还可以引申到其它的度量，如时间、费用、线路容量等。

算法
（一）单源最短路
(1)无负权边：Dijkstra算法
(2)有负权边：Bellman-Ford算法、SPFA算法
（二）多源最短路
Floyd算法

Dijkstra

Dijkstra算法适用于解决无负权边的单源最短路问题。Dijkstra算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

代码如下：

#include 
const int inf=0x3fffffff;//假设0x3fffffff为无穷大的值
int m,n,map[1005][1005],dis[1005],vis[1005];//m存点数，n存边数，map存图，dis存start到各点的距离，vis用来做标记（未被找过为0，找过为1）
int Min(int x,int y)
{return x<=y?x:y;
}
int Dijkstra(int start,int end)
{int i,j,min,flag;for(i=1;i<=m;i++)//开始时start到各点的距离均为无穷大dis[i]=inf;dis[start]=0;//start到自己的距离为0for(i=1;i<=m;i++){min=inf,flag=0;for(j=1;j<=m;j++){if(vis[j]==0&&min>dis[j])//找未被标记的点中距离最小的那一个点{min=dis[j];flag=j;}}vis[flag]=1;//标记距离最小的那一个点for(j=1;j<=m;j++){if(map[flag][j]==0)//如果从当前点无法到达目标点，则continue（剪枝操作，可略微优化算法）continue;if(vis[j]==0&&dis[j]>dis[flag]+map[flag][j])//找未被标记且可被优化的点dis[j]=dis[flag]+map[flag][j];//将其优化}}if(dis[end]==inf)//全部优化后到end的距离仍为inf，说明从start无法到达endreturn -1;return dis[end];
}
int main()//如果题目要跑循环，则需用memset函数将map数组、dis数组、vis数组清零
{int i,x,y,z,ans;scanf("%d%d",&m,&n);//m个点，n条边for(i=1;i<=n;i++){scanf("%d%d%d",&x,&y,&z);if(map[x][y]==0)map[x][y]=z;//如为双向图则加上map[y][x]=zelse//从x到y可能有多条路，取最短的那条路map[x][y]=Min(map[x][y],z);//如为双向图则加上map[y][x]=Min(map[y][x],z)}ans=Dijkstra(1,m);//题目让求哪个点到哪个点的最短路，参数就写几和几if(ans==-1)//从start无法到达endprintf("Impossible\n");elseprintf("%d\n",ans);return 0;
}

代码解释：
(1)inf的值为0x3fffffff：理论上，用inf来表示一个无穷大的数，inf的值应越大越好，但是在这里为什么inf的值是0x3fffffff而不是0x7fffffff呢？原因就是我们需要满足无穷大与无穷大的和仍为无穷大，如果用0x7fffffff的话则无法满足这一点，因为两个0x7fffffff相加的话会超过32位上限，会变为一个负数，而用0x3fffffff的话则可以满足这一点，两个0x3fffffff相加仍为无穷大（0x3fffffff*2+1==0x7fffffff）。

(2)flag的初始值为0：事实上，只要运行正确，flag的值一定是1~m之间的某个数，将它的初始值赋成0是为了防止运行错误导致vis数组由于下标flag不确定而引起的错误访问。

Bellman-Ford

Bellman-Ford算法适用于解决有负权边的单源最短路问题。

松弛
每次松弛操作实际上是对相邻节点的访问，第n次松弛操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过v-1条边，所以可知Bellman-Ford算法所得为最短路径。

负边权操作
与Dijkstra算法不同的是，Dijkstra算法的基本操作“拓展”是在深度上寻路，而“松弛”操作则是在广度上寻路，这就确定了Bellman-Ford算法可以对负边进行操作而不会影响结果。

负权环判定
因为负权环可以无限制的降低总花费，所以如果发现第n次操作仍可降低花销，就一定存在负权环。

由于Bellman-Ford算法可以被SPFA算法优化，所以Bellman-Ford算法用处不大，在这里就不贴代码了。

SPFA

SPFA算法同样适用于解决有负权边的单源最短路问题，只不过它使用了队列优化，使其时间复杂度降低。

负权环判定
如果某个点入队列次数大于n次表示图中有负环。

算法步骤
(1)建立一个队列，最初队列中只含有起点start。

(2)取出队首front，扫描它的所有出边(x,y,w)，若dis[x]+w

(3)重复上述步骤(2)，直到队列为空。

在任意时刻，该算法的队列都保存了待扩展的节点。每次入队相当于完成一次dis数组的更新操作，使其满足三角不等式，一个节点可能会入队、出队很多次。最终，图中的节点会收敛到全部满足三角不等式的状态。这个队列避免了Bellman-Ford算法中对不需要扩展的节点的冗余扫描。

代码如下：

#include 
#include 
#include 
using namespace std;
const int inf=0x3fffffff;//假设0x3fffffff为无穷大的值
int m,n1,n2,map[1005][1005],dis[1005],vis[1005],cnt[1005];//m存点数，n1存正边数，n2存负边数，map存图，dis存start到各点的距离，vis用来做标记（不在队列中为0，在队列中为1），cnt用来存各点的入队次数
int Min(int x,int y)
{return x<=y?x:y;
}
int SPFA(int start,int end)
{int i;queue <int> q;for(i=1;i<=m;i++)//开始时start到各点的距离均为无穷大dis[i]=inf;dis[start]=0,vis[start]=1,cnt[start]++;//start到自己的距离为0，标记为在队列中，入队次数加1q.push(start);while(q.empty()==0){start=q.front();q.pop();vis[start]=0;//出队则标记为不在队列中for(i=1;i<=m;i++){if(dis[i]>dis[start]+map[start][i])//如可优化则优化{dis[i]=dis[start]+map[start][i];if(vis[i]==0)//如果可优化的点不在队列中则入队{vis[i]=1,cnt[i]++;//标记为在队列中，入队次数加1q.push(i);if(cnt[i]>m)//如果入队次数大于点的个数则存在负环return -1;}}}}return dis[end];
}
int main()//如果题目要跑循环，则需用memset函数将map数组、dis数组、vis数组、cnt数组清零
{int i,x,y,z,ans;scanf("%d%d%d",&m,&n1,&n2);//m个点，n1条正边，n2条负边for(i=1;i<=n1;i++){scanf("%d%d%d",&x,&y,&z);if(map[x][y]==0)map[x][y]=z;//如为双向图则加上map[y][x]=zelse//从x到y可能有多条路，取最短的那条路map[x][y]=Min(map[x][y],z);//如为双向图则加上map[y][x]=Min(map[y][x],z)}for(i=1;i<=n2;i++){scanf("%d%d%d",&x,&y,&z);z=-z;if(map[x][y]==0)map[x][y]=z;//如为双向图则加上map[y][x]=zelse//从x到y可能有多条路，取最短的那条路map[x][y]=Min(map[x][y],z);//如为双向图则加上map[y][x]=Min(map[y][x],z)}ans=SPFA(1,m);//题目让求哪个点到哪个点的最短路，参数就写几和几if(ans==-1)//存在负环printf("存在负环！\n");elseprintf("%d\n",ans);return 0;
}

代码解释：
(1)inf的值为0x3fffffff：理论上，用inf来表示一个无穷大的数，inf的值应越大越好，但是在这里为什么inf的值是0x3fffffff而不是0x7fffffff呢？原因就是我们需要满足无穷大与无穷大的和仍为无穷大，如果用0x7fffffff的话则无法满足这一点，因为两个0x7fffffff相加的话会超过32位上限，会变为一个负数，而用0x3fffffff的话则可以满足这一点，两个0x3fffffff相加仍为无穷大（0x3fffffff*2+1==0x7fffffff）。

(2)vis数组的作用：vis数组用来记录某个点是否在队列中，例如vis[x]的值为0表示x点不在队列中，vis[x]的值为1表示x点在队列中。那么为什么可优化的点不在队列中就要把它加入到队列中呢？因为如果当前点可优化，则可以通过当前点继续去优化其它的点，如果当前点不在队列中就要把它加入到队列中去优化其它的点，如果当前点在队列中则随着程序的运行一定会有它出队去优化其它点的时候，所以如果当前点可优化并且不在队列中，就要把它加入到队列中。

(3)cnt数组的作用：cnt数组用来记录某个点的入队次数，例如cnt[x]的值为0表示x点入队过0次，cnt[x]的值为1表示x点入队过1次。不难证明，如果一共有m个点，其中的任何一个点入队超过m次，就证明存在负环，cnt数组是判断是否存在负环的关键。

Floyd

Floyd算法适用于解决多源最短路问题。

算法步骤
(1)从任意一条单边路径开始，所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

(2)对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比已知的路径更短，如果是更新它。

核心代码如下：

void Floyd(int m)//假设一共有m个点
{int i,j,k;for(k=1;k<=m;k++){for(i=1;i<=m;i++){if(map[i][k]==0)//如果从i无法到达k，就continue（剪枝操作，可略微优化算法）continue;for(j=1;j<=m;j++)if(map[i][j]>map[i][k]+map[k][j])//如可优化则优化map[i][j]=map[i][k]+map[k][j];}}
}

例题

Six Degrees of Cowvin Bacon

#include 
const int inf=0x3fffffff;
int a[305],map[305][305];
int main()
{int i,j,k,m,n,num,sum,min=0;scanf("%d%d",&m,&n);for(i=1;i<=m;i++){for(j=1;j<=m;j++){if(i!=j)map[i][j]=inf;elsemap[i][j]=0;}}while(n--){scanf("%d",&num);for(i=1;i<=num;i++)scanf("%d",&a[i]);for(i=1;i<=num-1;i++){for(j=i+1;j<=num;j++){if(map[a[i]][a[j]]>1)map[a[i]][a[j]]=1,map[a[j]][a[i]]=1;}}}for(k=1;k<=m;k++){for(i=1;i<=m;i++){if(map[i][k]==inf)continue;for(j=1;j<=m;j++)if(map[i][j]>map[i][k]+map[k][j])map[i][j]=map[i][k]+map[k][j];}}for(i=1;i<=m;i++)min+=map[1][i];for(i=2;i<=m;i++){sum=0;for(j=1;j<=m;j++)sum+=map[i][j];if(min>sum)min=sum;}printf("%d\n",(int)((double)(100*min/(m-1))));return 0;
}

典型的Floyd求多源最短路，注意图的存储，这题图的存储得两两相存，同时还得注意结果的类型，先取double型再取inti型。

Wormholes

#include 
#include 
#include 
#include 
using namespace std;
const int inf=0x3fffffff;
int n,m,w,map[505][505],dis[505],vis[505],cnt[505];
int spfa(int start)
{int i;queue <int> q;for(i=1;i<=n;i++)dis[i]=inf;dis[start]=0,vis[start]=1,cnt[start]++;q.push(start);while(q.empty()==0){start=q.front();q.pop();vis[start]=0;for(i=1;i<=n;i++){if(dis[i]>dis[start]+map[start][i]){dis[i]=dis[start]+map[start][i];if(vis[i]==0){vis[i]=1,cnt[i]++;q.push(i);if(cnt[i]>n)return 1;}}}}return 0;
}
int main()
{int i,j,s,e,t,num;scanf("%d",&num);while(num--){memset(vis,0,sizeof(vis));memset(cnt,0,sizeof(cnt));scanf("%d%d%d",&n,&m,&w);for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(i!=j)map[i][j]=inf;elsemap[i][j]=0;}}while(m--){scanf("%d%d%d",&s,&e,&t);if(map[s][e]>t)map[s][e]=t,map[e][s]=t;}while(w--){scanf("%d%d%d",&s,&e,&t);t=-t;if(map[s][e]>t)map[s][e]=t;}if(spfa(1))printf("YES\n");elseprintf("NO\n");}return 0;
}

典型的SPFA判断是否存在负环，题目问这个人是否可以完成穿越，如果存在负环则可以完成穿越，否则则不可以完成穿越。

Silver Cow Party

#include 
#include 
const int inf=0x3fffffff;
int n,m,x,map[1005][1005],dis[1005],dis_come[1005],dis_back[1005],vis[1005];
void Dijkstra(int start)
{int i,j,min,flag;memset(vis,0,sizeof(vis));for(i=1;i<=n;i++)dis[i]=inf;dis[start]=0;for(i=1;i<=n;i++){min=inf,flag=0;for(j=1;j<=n;j++)if(vis[j]==0&&min>dis[j])min=dis[j],flag=j;vis[flag]=1;for(j=1;j<=n;j++){if(map[flag][j]==inf)continue;if(vis[j]==0&&dis[j]>dis[flag]+map[flag][j])dis[j]=dis[flag]+map[flag][j];}}
}
int main()
{int i,j,a,b,c,t,max;scanf("%d%d%d",&n,&m,&x);for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(i!=j)map[i][j]=inf;elsemap[i][j]=0;}}for(i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&c);if(map[a][b]>c)map[a][b]=c;}Dijkstra(x);for(i=1;i<=n;i++)dis_back[i]=dis[i];for(i=1;i<n;i++){for(j=i+1;j<=n;j++){t=map[i][j];map[i][j]=map[j][i];map[j][i]=t;}}Dijkstra(x);for(i=1;i<=n;i++)dis_come[i]=dis[i];max=dis_come[1]+dis_back[1];for(i=2;i<=n;i++)if(max<dis_come[i]+dis_back[i])max=dis_come[i]+dis_back[i];printf("%d\n",max);return 0;
}

此题变相地利用了Dijkstra求最短路，要求某个点到x点以及x点到某个点的最短路之和（去和回走的道路不同，因为是有向图），然后求所有点中最短路最大的那一个是多少。做法就是先调用一遍Dijkstra，求x点到各点的最短路（相当于求了从x点回各点的最短路），把dis数组保存下来。然后把所有的路都反向（二维数组以主对角线为轴调换），再调用一遍Dijkstra，求x点到各点的最短路（相当于求了从各点去x点的最短路），再把dis数组保存下来。最后把保存的两个dis数组相加求最大值。注意每次调用Dijkstra都要把vis数组清零。

最短路

#include 
#include 
const int inf=0x3fffffff;
int m,n,map[105][105],dis[105],vis[105];
int Min(int x,int y)
{return x<=y?x:y;
}
int Dijkstra(int start,int end)
{int i,j,min,flag;for(i=1;i<=m;i++)dis[i]=inf;dis[start]=0;for(i=1;i<=m;i++){min=inf,flag=0;for(j=1;j<=m;j++)if(vis[j]==0&&min>dis[j])min=dis[j],flag=j;vis[flag]=1;for(j=1;j<=m;j++){if(map[flag][j]==0)continue;if(vis[j]==0&&dis[j]>dis[flag]+map[flag][j])dis[j]=dis[flag]+map[flag][j];}}return dis[end];
}
int main()
{int i,a,b,c,ans;while(scanf("%d%d",&m,&n)!=EOF){if(m==0&&n==0)break;memset(map,0,sizeof(map));memset(dis,0,sizeof(dis));memset(vis,0,sizeof(vis));for(i=1;i<=n;i++){scanf("%d%d%d",&a,&b,&c);if(map[a][b]==0){map[a][b]=c;map[b][a]=c;}else{map[a][b]=Min(map[a][b],c);map[b][a]=Min(map[a][b],c);}}ans=Dijkstra(1,m);printf("%d\n",ans);}return 0;
}

典型的Dijkstra求最短路。

Til the Cows Come Home

#include 
const int inf=0x3fffffff;
int m,n,map[1005][1005],dis[1005],vis[1005];
int Min(int x,int y)
{return x<=y?x:y;
}
int Dijkstra(int start,int end)
{int i,j,min,flag;for(i=1;i<=n;i++)dis[i]=inf;dis[start]=0;for(i=1;i<=n;i++){min=inf,flag=0;for(j=1;j<=n;j++)if(vis[j]==0&&min>dis[j])min=dis[j],flag=j;vis[flag]=1;for(j=1;j<=n;j++){if(map[flag][j]==0)continue;if(vis[j]==0&&dis[j]>dis[flag]+map[flag][j])dis[j]=dis[flag]+map[flag][j];}}return dis[end];
}
int main()
{int i,a,b,c,ans;scanf("%d%d",&m,&n);for(i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&c);if(map[a][b]==0){map[a][b]=c;map[b][a]=c;}else{map[a][b]=Min(map[a][b],c);map[b][a]=Min(map[a][b],c);}}ans=Dijkstra(n,1);printf("%d\n",ans);return 0;
}

典型的Dijkstra求最短路，注意这题是先取的边数再取的点数。

Heavy Transportation

#include 
#include 
int m,n,map[1005][1005],dis[1005],vis[1005];
int Min(int x,int y)
{return x<=y?x:y;
}
int Dijkstra(int start,int end)
{int i,j,max,flag;for(i=1;i<=m;i++)dis[i]=map[start][i];dis[start]=0;for(i=1;i<=m;i++){max=0,flag=0;for(j=1;j<=m;j++)if(vis[j]==0&&max<dis[j])max=dis[j],flag=j;vis[flag]=1;for(j=1;j<=m;j++){if(map[flag][j]==0)continue;if(vis[j]==0&&dis[j]<Min(dis[flag],map[flag][j]))dis[j]=Min(dis[flag],map[flag][j]);}}return dis[end];
}
int main()
{int i,j,a,b,c,t,ans;scanf("%d",&t);for(i=1;i<=t;i++){memset(map,0,sizeof(map));memset(dis,0,sizeof(dis));memset(vis,0,sizeof(vis));scanf("%d%d",&m,&n);for(j=1;j<=n;j++){scanf("%d%d%d",&a,&b,&c);map[a][b]=c;map[b][a]=c;}ans=Dijkstra(1,m);printf("Scenario #%d:\n",i);printf("%d\n\n",ans);}return 0;
}

此题为Dijkstra的逆用，先找到未被标记且重量最大的点，将其标记后用其去优化其它的点。优化的过程为如果某个点未被标记且目前它的重量小于当前点的重量和当前点到这个点的道路的重量的小者，则将这个点的重量优化为当前点的重量和当前点到这个点的道路的重量的小者。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！