图论--最短路径问题

最短路径问题

一、最短路径算法：

首先介绍多源最短路径算法（求任意两点之间的最短路径）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数组判断此点是否已经被“松弛”。