赞
踩
Floyed、Dijkstra、Bellman-Ford、SPFA可以有效地解决最短路径问题。
需要注意的是:边的权值可以为负。当出现负边权时,有些算法不适用
最短路径问题是图论中典型的问题,多数模型可以归结为一下三种
国庆期间,7535寝室计划去旅行。在出发前,寝室长查阅了地图,如下图,寝室长希望在出发前知道任意两个城市之间的最短路径。
那么,如何求解任意两点之间的最短路径呢?
分析:如果要让任意两点之间(假设是a到b)的路程变短,只能引入第三个点(假设为k),通过点k进行中转即a -> k -> b,才可能缩短原来从顶点a到顶点b的路程。如在上图中,结点1到结点3的距离本来为6,但是引入结点2之后,这两个结点的距离就变为了5。有时候可能还不只一个中转点,而是经过两个点或者更多的点进行中转会更短,即a -> k1 -> k2 -> b或者a -> k1 -> k2 -> … …-> b。
例如:在不考虑其他结点的情况下,上图中的4号城市到3号城市的路程原本是e[4][3] = 12
,但是如果通过1号城市中转4 -> 1 -> 3,那么路程将缩短为11(e[4][1] + e[1][3] = 5 + 6 = 11
)。如果同时通过1号和2号两个城市中转的话,从4号城市到3号城市的路程会进一步缩短为10(e[4][1] + e[1][2] + e[2][3] = 5 + 2 + 3 = 10
)。通过以上分析,我们发现每个顶点都有可能使得另外两个顶点之间的路程变短。模拟该过程:
首先,如何存储这个地图?
可以用一个二维数组e来存储。比如1号城市到2号城市的路程为2,则设e[1][2] = 2
。2号城市无法直接到达4号城市, 则设e[2][4] = ∞
。另外,约定自己到自己的路程为0。最终,得到表示两个城市之间距离的二维数组:
假设现在只允许经过1号顶点中转,求任意两点之间(i
到j
)的最短路径。只需要判定经过1号顶点中转的距离e[i][1] + e[1][j]
是否比 i 到 j 的初始距离e[i][j]
小。代码如下:
//经过1号顶点中转
for(i = 1;i <= n;i++)
{
for(j = 1;j <= n;j++)
{
//if (i到j的初始距离e[i][j] > 经过1号顶点中转的距离) 更新
if(e[i][j] > e[i][1] + e[1][j])
e[i][j] = e[i][1] + e[1][j];
}
}
在只经过1号中转的情况下,任意两点之间的最短路径更新为下图:
既然可以允许经过1号结点中转,那么是否可以允许经过2号结点中转?显然是可以的。接下来,允许2号结点作为中转结点,任意两点之间的最短路径怎么求?我们需要在允许1号顶点作为中转结点的情况下,再判断允许2号顶点作为中转结点,是否可以使得 i 号顶点到 j 号顶点之间的路程变得更短,即判断经过2号结点之后的路程e[i][2] + e[2][j]
是否比不经过2号结点的路程e[i][j]
要小,代码如下:
//经过2号顶点中转
for(i = 1;i <= n;i++)
{
for(j = 1;j <= n;j++)
{
if(e[i][j] > e[i][2] + e[2][j])
e[i][j] = e[i][2] + e[2][j];
}
}
在经过1号和2号的中转的情况下,任意两点之间的最短路径更新为下图:
根据这样的规则,依次经过1号,2号,3号,4号四个顶点中转的情况下,求任意两点之间的最短路径,代码如下:
//经过1号顶点中转 for(i = 1;i <= n;i++) for(j = 1;j <= n;j++) { if(e[i][j] > e[i][1] + e[1][j]) e[i][j] = e[i][1] + e[1][j];//经过1号结点中转之后距离变小,更新 } //经过2号顶点中转 for(i = 1;i <= n;i++) for(j = 1;j <= n;j++) { if(e[i][j] > e[i][2] + e[2][j]) e[i][j] = e[i][2] + e[2][j];//经过2号结点中转之后距离变小,更新 } //经过3号顶点中转 for(i = 1;i <= n;i++) for(j = 1;j <= n;j++) { if(e[i][j] > e[i][3] + e[3][j]) e[i][j] = e[i][3] + e[3][j];//经过3号结点中转之后距离变小,更新 } //经过4号顶点中转 for(i = 1;i <= n;i++) for(j = 1;j <= n;j++) { if(e[i][j] > e[i][4] + e[4][j]) e[i][j] = e[i][4] + e[4][j];//经过4号结点中转之后距离变小,更新 }
以上过程较繁琐,我们可以将以上过程写成三个for循环,代码如下:
for(k = 1;k <= n;k++) //依次经过1~n中的n个点进行中转
for(i = 1;i <= n;i++)
for(j = 1;j <= n;j++)
{
if(e[i][j] > e[i][k] + e[k][j])
e[i][j] = e[i][k] + e[k][j];
}
需要强调的是:用来循环中间点的变量k必须放在最外面一层循环
最终,得到任意两个结点之间的最短路径,如图所示:
Floyed算法总结:
Floyed算法可以算出任意两点的最短路径,可以处理带有负权边的图,但不能处理带有“负环”的图
什么是负环?如图所示:
e[1][1]
本应等于0,如果采用Floyed算法更新最短路,e[1][1] = 2 + 3 - 6 = -1
Floyed算法的时间复杂度:O(n^3)
Floyed算法例题:
题目描述
平面上有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,分别表示源点和目标点。
输出
一行,一个实数(保留两位小数),表示从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
AC代码:
本题需要注意的是,对于double数组,需要循环手动赋值无穷,而不能用memset
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> using namespace std; const int inf = 0x3f3f3f3f; const int N = 110; double e[N][N];//e[i][j]表示结点i到结点j的最短距离 struct node { int x;//横坐标 int y;//纵坐标 }pos[N]; int main() { //memset(e,inf,sizeof e); int n,m; scanf("%d",&n);//表示结点的个数 for (int i = 1;i <= n;i++) scanf("%d%d",&pos[i].x,&pos[i].y);//输入第i个结点的横纵坐标 for (int i = 1;i <= n;i++) for (int j = 1;j <= n;j++) e[i][j] = inf; scanf("%d",&m); while (m --) { int p,q; scanf("%d%d",&p,&q);//连接两点 double del_x = pos[p].x - pos[q].x;//第p个结点和第q个结点的横坐标之差 double del_y = pos[p].y - pos[q].y;//第p个结点和第q个结点的纵坐标之差 e[p][q] = e[q][p] = sqrt((double)pow(del_x,2) + (double)pow(del_y,2));//计算距离 } for (int i = 1;i <= n;i++) e[i][i] = 0;//初始化 //Floyed算法模板 for (int k = 1;k <= n;k++) for (int i = 1;i <= n;i++) for (int j = 1;j <= n;j++) e[i][j] = min(e[i][j],e[i][k] + e[k][j]); int start,end; scanf("%d%d",&start,&end); printf("%.2f",e[start][end]); return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。