欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图论--最短路径问题

程序员文章站 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数组判断此点是否已经被“松弛”。

上一篇:

下一篇: