[数据结构] 图---求解多源最短路径：实现弗洛伊德算法

弗洛伊德算法

• 解决图中任意两点之间的最短路径问题
• 具体实现：
  vvdist矩阵存放任意两个顶点间的最短路径长度（初始为正无穷）
  vvparentPath矩阵存放任意两个顶点路径间，最后一个顶点的前一个结点的下标（初始为-1）

void FloydWarShall(vector<vector<W>>& vvdist, vector<vector<int>>& vvparentPath){
		size_t n = _vertex.size();
		//初始化两个矩阵
		vvdist.resize(n);
		vvparentPath.resize(n);
		for (size_t i = 0; i < n; i++){
			vvdist[i].resize(n, MAX_W);
			vvparentPath[i].resize(n, -1);
		}

		//更新直接相连的两条边，与matrix数组有关
		for (size_t i = 0; i < n; i++){
			for (size_t j = 0; j < n; j++){
				if (i == j){
					vvdist[i][j] = 0;
				}
				if (_matrix[i][j] != MAX_W){
					vvdist[i][j] = _matrix[i][j];
					vvparentPath[i][j] = i;
				}
			}
		}

		//更新最短路径（动规的思想）
		for (size_t k = 0; k < n; k++){
			for (size_t i = 0; i < n; i++){
				for (size_t j = 0; j < n; j++){
					//若i->j路径上，经过k时路径更小，则更新
					if (vvdist[i][k] != MAX_W && vvdist[k][j] != MAX_W 
						&& vvdist[i][k] + vvdist[k][j] < vvdist[i][j]){
						vvdist[i][j] = vvdist[i][k] + vvdist[k][j];
						//若k->j相连，上一个结点为k，vvparentPath[k][j]==k；
						//若不相连，k->..->x->j，上一个结点为x，vparentPath[k][j]==x
						vvparentPath[i][j] = vvparentPath[k][j];
					}
				}
			}
		}
	}
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