floyd算法

缘起

floyd算法是求有向非负权网任意两点之间的最短路径.

分析

Floyd算法又叫做Floyd-Warshall算法.

Floyd算法其实就是一种动态规划+滚动数组降低空间复杂度的算法

邻接矩阵adjMatrix[i][j][k](简记A[i][j][k])表示允许借助顶点1,2,…,k中转产生的从顶点i到顶点j的最短距离
则dp模型是

对于固定的i和j, 有如下式子成立

1
A[i][j][k]=min{A[i][j][k-1],A[i][k][k-1]+A[k][j][k-1]}

可以看成是上一层的k 由下一层的k-1取min决定, 所以k是最外层循环. 下层k决定上层k

也就是说,A[i][j][k]是A[i][j][k-1](不借助顶点k进行中转)与A[i][k][k-1]+A[k][j][k-1](借助顶点k进行中转)的较小值,

但是注意到上述模型可知，可以用二维（滚动）数组而不是三维数组来得到最小值，这样就降低了空间复杂度

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
#include "stdafx.h"
#include <iostream>
#pragma warning(disable:4996)

#define LOCAL
using namespace std;
const int MAX_NUM = 20;
const int INF = 0x3f3f3f3f;

struct Graph
{
	int n;
	int adj[MAX_NUM][MAX_NUM];

	Graph()
	{
		puts("输入顶点的个数");
		scanf("%d", &n);
		puts("输入边的起点, 终点, 权重.");
		memset(adj, 0x3f, sizeof(adj));
		for (int i = 1; i<=n;i++) adj[i][i] = 0;
		int x,y,w;
		while(~scanf("%d%d%d", &x, &y, &w)) adj[x][y] = w;
	}

	void floyd() {for (int k = 1; k<=n; k++) for (int i = 1; i<=n; i++)for (int j = 1; j<=n; j++)adj[i][j] = min(min(adj[i][j], adj[i][k]+adj[k][j]),INF);}  // floyd最短路径算法(仅仅一行代码),注意, 小于INF是为了防止INF+2*INF超出最大整型
};


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	Graph g;
	g.floyd();
	for (int i = 1;i<=g.n;i++)
	{
		for (int j = 1;j<=g.n;j++)
		{
			printf("%d到%d的最短路径是%d\n", i,j, g.adj[i][j]);
		}
	}
	return 0;
}
/*
测试数据
4
1 2 2
2 3 3
1 3 6
3 1 7
1 4 4
4 1 5
3 4 1
4 3 12
*/

floyd 算法的时间复杂度是 O(N^3)的. 所以N不大的时候, 相当可以. 因为代码简单， 而且和dijkstra算法不一样的地方在于, floyd可以求出任意两点之间的距离.