百度网站排名怎么做,网销怎么找客户,直播网站功能怎么做,网站目录文件查看最短路径问题(floyed.cpp dijkstra.cpp) 题目描述平面上有n个点(n100)#xff0c;每个点的坐标均在-10000#xff5e;10000之间。其中的一些点之间有连线。若有连线#xff0c;则表示可从一个点到达另一个点#xff0c;即两点间有通路#xff0c;通路的距离为两点间的… 最短路径问题(floyed.cpp dijkstra.cpp) 题目描述平面上有n个点(n100)每个点的坐标均在-1000010000之间。其中的一些点之间有连线。若有连线则表示可从一个点到达另一个点即两点间有通路通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。输入 第1行1个整数n 第2..n1行每行2个整数x和y描述了一个点的坐标 第n2行1个整数m表示图中连线的数量 接下来有m行每行2个整数i和j表示第i个点和第j个点之间有连线 最后1行2个整数s和t分别表示源点和目标点输出 第1行1个浮点数表示从s到t的最短路径长度保留2位小数样例输入 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 #------------------------------------------------------------------------------# 最短路径也是有很多方法的这里就讲讲Floyed和Dijkstra。 Floyed 这种算法比较好理解且可以求任意两点间的最短路径但速度很慢为O(N^3)。 首先需要k[i][j]存从第i点到第j点间的最短路径如果它们不相连则为∞无穷大在这里可以设为0x7fffffff0x表示后面的数为16进制7fffffff即是16进制数化为10进制等于2147483647。 然后需要3层循环第一层需要经过的点p第二、三层起点i和终点j然后就开始推很像动规的“状态转移方程”为k[i][j]min(k[i][j],k[i][p]k[p][j]) 这样不用考虑两点没联通的情况吗之前的∞就有作用了如果两点没联通的话是赋不了值的。 代码Floyed #includecstdio
#includecmath
struct p
{int x,y;
}a[102];//这个结构体是存平面直角坐标系的
int f[102][102];
double k[102][102];
int n,m,hhd;
int main()
{//freopen(floyed.in,r,stdin);//freopen(floyed.out,w,stdout);//文件输入输出int b,e;scanf(%d,n);for(int i1;in;i)scanf(%d%d,a[i].x,a[i].y);scanf(%d,m);for(int i1;im;i){int x,y;scanf(%d%d,x,y);f[x][y]f[y][x]1;//邻接数组标记}scanf(%d%d,b,e);for(int i1;in;i)for(int j1;jn;j)if(f[i][j])//如果两点有连接k[i][j]sqrt(pow(a[i].x-a[j].x,2.0)pow(a[i].y-a[j].y,2.0));//求两点距离存入k数组elsek[i][j]0x7fffffff;//反之则设为极大值for(int p1;pn;p)for(int i1;in;i)for(int j1;jn;j)if(k[i][j]k[i][p]k[p][j])k[i][j]k[i][p]k[p][j];//开始算法printf(%.2lf,k[b][e]);//输出从起点b到终点e的最短路径return 0;
}----我只是个小分割线---- Dijkstra 此算法较只是较前一种快时间复杂度为O(N^2)注意它不能处理负边权的情况。 而且这个只能求从一个起点单源点到其他任何点的距离但解决这道题足够了。 一个一维数组dis[i]表示起点到i点的最短距离k数组与上同还需要一个bool数组判断该点是否用过。 思路从起点到某个点一定会经过一个及以上的“中间点”可以发现从起点到i点的最短路径中的每一个“中间点”到起点的距离都是相等的就像动态规划的“最优子结构”性质所以只要找出每个点的最短路径即可知道起点到终点的最短路径。 为什么不能处理负边权呢 如图假如想要从1到3最短的显然为1-2-3共-2但Dijkstra算法会先选择直接到3因为这样为1所以答案错误。 代码Dijkstra #includecstdio
#includecmath
#includecstring
struct p
{int x,y;
}a[102];
int _f[102][102];
bool f[102];
double k[102][102],dis[102];
int n,m;
int main()
{//freopen(dijkstra.in,r,stdin);//freopen(dijkstra.out,w,stdout);int b,e;scanf(%d,n);for(int i1;in;i)scanf(%d%d,a[i].x,a[i].y);scanf(%d,m);for(int i1;im;i){int x,y;scanf(%d%d,x,y);_f[x][y]_f[y][x]1;}for(int i1;in;i)for(int j1;jn;j)if(_f[i][j])k[i][j]sqrt(pow(a[i].x-a[j].x,2.0)pow(a[i].y-a[j].y,2.0));elsek[i][j]0x7fffffff;//以上与Floyed相同scanf(%d%d,b,e);f[b]1;for(int i1;in;i)dis[i]k[b][i];//将距离存进去for(int i1;in-1;i){int p0x7fffffff,w0;//p为当前最小值w为“中间点”下标for(int j1;jn;j)if(f[j]0dis[j]p){wj;pdis[j];//更新最小值}//查找“中间点”if(w0)break;//如果全部没有则表示找完了f[w]1;//标记此点已用for(int j1;jn;j)if(dis[w]k[w][j]dis[j])dis[j]dis[w]k[w][j];//开始找进过w的最小值}printf(%.2lf,dis[e]);//输出return 0;
}By WZY转载于:https://www.cnblogs.com/LinqiongTaoist/p/7203760.html
