最短路径算法解析

通过公交专用APP预设路线，自动计算最短路径 #生活技巧# #节省生活成本# #出行省钱建议# #公交时刻表优化#

最短路径问题

题目

平面上有n个点(N<=100)，每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点直线的距离。现在的任务是找出从一点到另一点之间的最短路径。

输入

输入共有n+m+3行，其中：
第一行为一个整数n。
第2行到第n+1行（共n行），每行的两个整数x和y，描述一个点的坐标(以一个空格隔开)。
第n+2行为一个整数m，表示图中的连线个数。
此后的m行，每行描述一条连线，由两个整数I,j组成，表示第i个点和第j个点之间有连线。
最后一行：两个整数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 12345678910111213

输出

输出仅一行，一个实数(保留两位小数)，表示从S到T的最短路径的长度。

输出样例

3.41 1

这道题有四种方法。

思路1：Floyed-Warshall算法

这道题我们用Floyed-Warshall算法来做。

Floyed-Warshall算法的思路是这样的：

三层循环，第一层循环中间点k，第二第三层循环起点终点i、j，算法的思想很容易理解：如果点i到点k的距离加上点k到点j的距离小于原先点i到点j的距离，那么就用这个更短的路径长度来更新原先点i到点j的距离。

先求出所有连通的两点的长度，然后用Floyed-Warshall算法，就OK了。

但是，有一个问题：如何求连通的两点的距离？
在这里，我们就要用到勾股定理了。

设两点坐标分别为（x1,y1）（x2,y2），则两点距离=
s q r t ( ( x 1 − y 1 ) 2 + ( x 2 − y 2 ) 2 ) sqrt((x1-y1)^2+(x2-y2)^2) sqrt((x1−y1)2+(x2−y2)2)

代码

#include<cstdio> #include<cmath> #include<iostream> using namespace std; int n,m,x,y,s,t,a[101][2];//初始化 double f[101][101];//初始化（距离有小数，所以用double） int main() {memset(f,0x7f,sizeof(f));//先把f调成一个比较大的数，以便求最小 //注意：不能调成最大值，不然后面加起来会炸scanf("%d",&n);//读入for (int i=1;i<=n;i++)//枚举每一个点scanf("%d%d",&a[i][1],&a[i][2]);//读入scanf("%d",&m);//读入for (int i=1;i<=m;i++)//枚举每两个连通的点{scanf("%d%d",&x,&y);//读入f[y][x]=f[x][y]=sqrt(double(a[x][1]-a[y][1])*double(a[x][1]-a[y][1])+double(a[x][2]-a[y][2])*double(a[x][2]-a[y][2]));//求出这两点之间的距离（因为是无向图，所以其对称点也要求）}scanf("%d%d",&s,&t);//读入for (int k=1;k<=n;k++)//枚举分割点for (int i=1;i<=n;i++)//枚举一个点if (i!=k)//分割点不能和那个点相同for (int j=1;j<=n;j++)//枚举另一个点if(i!=j&&k!=j)//这个点也不可以和分割点和之前那个点相同f[i][j]=min(f[i][k]+f[k][j],f[i][j]);//求出这两个点之间的最短距离printf("%.2lf",f[s][t]);//输出（保留两位小数）return 0; }

123456789101112131415161718192021222324252627282930

思路2：Dijkstra算法

这次，我们用Dijkstra算法来做。

Dijkstra算法的思路是这样的：

一开始将起点到起点的距离标记为0，接着用n次循环，把离新标记为0的点最近的另一个点也标记。接着枚举所以未标记点，如果以此点为中转到达未标记点的路径更短的话，这将成为从此点到未标记点“最短路径”（但不确定，到时可能会有更好的方法）。

那么，先求出所有连通的两点的长度，然后用Dijkstra算法，就OK了。

注意

Dijkstra算法不能处理负边权的情况哦！

代码

#include<cstdio> #include<iostream> #include<cstring> #include<cmath> using namespace std; int n,m,s,t,a[101][2],l;//初始化 bool c[101];//初始化 double minn,f[101][101],b[101];//初始化 int main() {memset(f,0x7f,sizeof(f));//把f弄成一个较大的数，以便求最小 //注意：不能调成最大值，不然后面加起来会炸scanf("%d",&n);//读入for (int i=1;i<=n;i++)//枚举每一个点scanf("%d%d",&a[i][1],&a[i][2]);//读入scanf("%d",&m);//读入for (int i=1;i<=m;i++)//枚举每两个连通的点{scanf("%d%d",&s,&t);//读入f[t][s]=f[s][t]=sqrt(double((a[s][1]-a[t][1])*(a[s][1]-a[t][1]))+double((a[s][2]-a[t][2])*(a[s][2]-a[t][2])));//求出这两点之间的距离（因为是无向图，所以其对称点也要求）}scanf("%d%d",&s,&t);//读入for (int i=1;i<=n;i++)//枚举一个点b[i]=f[s][i];//求出从s点到每一个点的距离b[s]=0;//预处理c[s]=1;//预处理for (int j=2;j<n;j++)//枚举要求的每一个点 //（点s已处理，剩下一个不用再求）{minn=f[0][0];//附一个较大的值，以便求最小l=0;//预处理for (int i=1;i<=n;i++)//枚举每一个点if (!c[i]&&b[i]<minn)//判断此点是否处理过，处理过就不能用了。{minn=b[i];//结合上面的if求出最小的l=i;//如有则标记有更优}if (!l) break;//如没有更优则一定搜完了，退出c[l]=1;//标记已完成for (int i=1;i<=n;i++)//枚举每一个点if (b[l]+f[l][i]<b[i]&&!c[i])//如果与这个点连通且未标记并且更短b[i]=b[l]+f[l][i];//把它设为“最短路径”}printf("%.2lf",b[t]);//输出return 0; }

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647

思路3：Bellman-Ford算法

这次，我们用Bellman-Ford算法来做。

Bellman-Ford算法的思路是这样的：

一开始标记起点为0，每次枚举所有边，找到一些连接标记点和未标记点的边。就以这样的方式去标记未标记点。当然，每次循环也必然会有至少一个未标记点被标记。

我们先求出所有连通的两点的长度，然后用Bellman-Ford算法，就OK了。

代码

#include<cstdio> #include<iostream> #include<cstring> #include<cmath> using namespace std; int n,m,x,y,f[1001][2],a[1001][2];//初始化 double c[1001],b[1001];//初始化 int main() {memset(c,0x7f,sizeof(c));//把c设为一个较大的 //注意：不能调成最大值，不然后面加起来会炸scanf("%d",&n);//读入for (int i=1;i<=n;i++)//枚举每一个点scanf("%d%d",&a[i][1],&a[i][2]);//读入scanf("%d",&m);//读入for (int i=1;i<=m;i++)//枚举每两个连通的点{scanf("%d%d",&x,&y);//读入f[i][1]=x;f[i][2]=y;//记录这个边的两个点b[i]=sqrt(double((a[x][1]-a[y][1])*(a[x][1]-a[y][1]))+double((a[x][2]-a[y][2])*(a[x][2]-a[y][2])));//求出这两点之间的距离}scanf("%d%d",&x,&y);//读入c[x]=0;//预处理for (int i=1;i<=n;i++)//枚举点for (int j=1;j<=m;j++)//枚举边{if (c[f[j][1]]+b[j]<c[f[j][2]]) c[f[j][2]]=c[f[j][1]]+b[j];//如果有更短的方法则把它设为“最短路径”if (c[f[j][2]]+b[j]<c[f[j][1]]) c[f[j][1]]=c[f[j][2]]+b[j];//因为是无向图，所以要弄一次对称的}printf("%.2lf",c[y]); //输出return 0; }

123456789101112131415161718192021222324252627282930313233

思路4：SPFA算法

这次，我们用SPFA算法来做。

SPFA算法的思路是这样的：

初始时将起点加入队列。每次从队列中取出一个元素，并对所有与它相邻的点进行修改，若某个相邻的点修改成功，则将其入队。直到队列为空时算法结束。
其实SPFA简单的说就是队列优化的bellman-ford。

我们先求出所有连通的两点的长度，然后用SPFA算法，就OK了。
当然，这就需要用到邻接表和STL的队列了。

代码

#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<queue> using namespace std; struct note {int x,next; }e[2001];//初始化 int n,m,ls[2001],x[2001],y[2001],s,t,k;//初始化 double a[2001][2001],an[2001];//初始化 bool in[2001];//初始化 int main() {memset(an,0x7f,sizeof(an));//把an设为一个较大的值memset(a,1e9,sizeof(a));//把a也设为一个较大的值scanf("%d",&n);//读入for (int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);//读入scanf("%d",&m);//读入for (int i=1;i<=m;i++){scanf("%d%d",&s,&t);//读入double l=(double)x[s]-x[t];double r=(double)y[s]-y[t];a[s][t]=a[t][s]=sqrt(l*l+r*r);//求两点距离e[++k]=(note){s,ls[t]};ls[t]=k;e[++k]=(note){t,ls[s]};ls[s]=k;//建邻接表}scanf("%d%d",&s,&t);//读入queue<int>l;//建队列an[s]=0;//赋初值l.push(s);//将起点加入队列while (!l.empty())//判断队列是否为空，如为空则表明已求完{int hh=l.front();//取出头元素l.pop();//弹出头元素for (int i=ls[hh];i;i=e[i].next)//枚举与其点相邻的点if (an[e[i].x]>an[hh]+a[hh][e[i].x])//判断是否有有更短的方法{an[e[i].x]=an[hh]+a[hh][e[i].x];//如果有更短的方法则把它设为“最短路径”if (!in[e[i].x])//判断是否在队伍中{l.push(e[i].x);in[e[i].x]=1;//如没有则入队}}in[hh]=0;//把头元素标记为不在队列中（因为之前已弹出）}printf("%.2lf",an[t]);//输出return 0; }

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152

网址：最短路径算法解析 https://www.yuejiaxmz.com/news/view/554323

相关内容

旅游省钱大法：加权最短路径
arcpy 最短路径
扫地机器人路径规划算法解读
解码人生算法：揭秘如何优化你的生活路径与决策技巧
【创新未发表】基于鱼鹰OOA求解带时间窗的骑手外卖配送路径规划问题，最优路径成本附Matlab代码
算法设计与分析
节约法用于车辆路径问题的综述和分析
路径规划的方法
AI智能规划：一键生成完整路径解决方案，满足多样化出行需求
一种基于通勤出行的顺风车共享合乘路径匹配方法

随便看看