图论--最短路径问题
程序员文章站
2023-12-27 13:48:15
...
最短路径问题
一、最短路径算法:
首先介绍多源最短路径算法(求任意两点之间的最短路径)Floyd–Warshall算法
时间复杂度O(n^3)
以下图为例,下面是Floyd–Warshall详解
我们假设当任意两点之间不允许经过第三个点时,这些城市之间的最短路程就是原图不变。(个点之间的直线距离最短)
现在假设任意两点之间的最短路径必须经过顶点1,然后求最短路程。
只需要判断e[i][1]+e[1][j]与e[i][j]的大小就可以了。
(其中,e[i][1]表示从i到1的路程、e[1][j]表示从1到j的路程、e[i][j]表示从i到j的路程)
实现代码如下:
void solve()
{
for(int i=1;i<=V;i++)
for(int j=1;j<=V;j++)
e[i][j]=min(e[i][1]+e[1][j],e[i][j]);
}
这时候、我们的邻接矩阵变成了:
这时有些距离已经短了。
接下来继续求只允许经过1和2号两个顶点的情况。
同上面的步骤、只需要在求完只允许经过顶点1的最短路程后、再继续求如果经过2号顶点的情况即可。
实现代码如下:
void solve()
{
//经过1号顶点
for(int i=1;i<=V;i++)
for(int j=1;j<=V;j++)
e[i][j]=min(e[i][1]+e[1][j],e[i][j]);
//经过2号顶点
for(int i=1;i<=V;i++)
for(int j=1;j<=V;j++)
e[i][j]=min(e[i][2]+e[2][j],e[i][j]);
}
这时候路程更新为:
综上:
最后允许所有的点作为中转、只需要加个大循环就可以了。
实现代码为:
void Floyd_Warshall()
{
for(int k=1;k<=V;k++)
for(int i=1;i<=V;i++)
for(int j=1;j<=V;j++)
e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
}
此时的图:全部为最短路径。
注意:弗洛伊德算法不能解决“负权回路”的问题。
介绍另一种最短路算法:Dijkstra算法!
该算法的核心思想是通过边“松弛”。主要解决单源最短路径问题(从某个顶点到其余各个顶点的路程)。
以这个的图为例:我们求从1号顶点到其余各个顶点的最短路程。
1、与Floyd算法一样、我们需要一个邻接矩阵e[MAXN][MAXN]存储图;
2、还需要一个一维数组存储dis[MAXN]存储从1号顶点到其余各个顶点的最短路程;
3、一个book数组判断此点是否已经被“松弛”。