图的最短路径：Floyd算法

有些城市之间有公路，有些没有，为了节省时间经费，希望找到任意两个城市之间的最短路径。如下图：

如何求两点之间的最短路径？

  • 要让任意两点之间的路径变短，只能尝试引入其他点，并通过中转才可能缩短距离
  • 当任意两点间不允许经过第三个点时，城市之间的最短路径就是初始路径
  • 可以逐步允许某个点进行中转，最后找出最短路径

解题代码

整体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//最短路径——弗洛伊德算法
#include<iostream>
using namespace std;
#define inf 999999;//定义无穷大

int city, road;
//城市数量和道路数量

//弗洛伊德算法
void floyd(int** cityMap)
{
	for (int i = 1; i <= city; i++)//允许经过第i个点的情况下
	{
		for (int j = 1; j <= city; j++)//从第j个点
		{
			for (int k = 1; k <= city; k++)//到第k个点
			{
				if (cityMap[j][k] > cityMap[j][i] + cityMap[i][k])//比较距离
					cityMap[j][k] = cityMap[j][i] + cityMap[i][k];
			}
		}
	}
}

int main()
{
	cin >> city >> road;
	//初始化地图
	int** cityMap = new int*[city + 1];
	for (int i = 0; i < city + 1; i++)
	{
		cityMap[i] = new int[city + 1];
		for (int j = 0; j < city + 1; j++)
		{
			cityMap[i][j] = inf;
		}
	}
	for (int i = 1; i <= city; i++) cityMap[i][i] = 0;

	//录入地图数据
	int a, b,c;
	for (int i = 0; i < road; i++)
	{
		cin >> a >> b >> c;
		cityMap[a][b] = c;
	}

	floyd(cityMap);//最短路径

	//输出结果
	for (int i = 1; i <= city; i++)
	{
		for (int j = 1; j <= city; j++)
		{
			cout << cityMap[i][j];
		}
		cout << endl;
	}
	return 0;
}

核心算法思路

1
2
3
4
5
6
7
8
9
10
11
for (int i = 1; i <= city; i++)//允许经过第i个点中转的情况下
{
	for (int j = 1; j <= city; j++)//从第j个点
	{
		for (int k = 1; k <= city; k++)//到第k个点
		{
			if (cityMap[j][k] > cityMap[j][i] + cityMap[i][k])//比较距离
			    cityMap[j][k] = cityMap[j][i] + cityMap[i][k];
		}
	}
}

可以看到Floyd算法的三层循环：

  1. 第一层：在允许第i个点进行中转的情况下
  2. 第二层：从第j个点
  3. 第三层：到第k个点，比较距离：
    • 如果距离jk大于距离ji+距离ik，则说明在原有基础上经过第i个点中转可以使路径变短，更新一下最短路径

Floyd算法可以处理带有负权边的图，但不能处理带有负权回路的图