算法分析与设计-作业2-Floyd算法求最短距离

1.问题

用Floyd算法求解下图各个顶点的最短距离。

2.解析

(1)用一个邻接矩阵A来存放各个边的长度
(2)递推产生一个矩阵序列，Ak(i,j)表示从顶点vi到vj的路径上所经过的顶点***不大于k的最短路径长度，迭代公式：

(3)当k==n，An就是顶点之间的最短通路值；

结果如下：

3.设计

	//核心部分
	for (k = 0; k < n; ++k) {
		for (i = 0; i < n; ++i) {
			for (j = 0; j < n; ++j) {
				if (k==i||k==j)
					continue;

				if (A[i][k] + A[k][j] < A[i][j]) {
					A[i][j] = A[i][k] + A[k][j];
					path[i][j] = path[k][j];
				}
			}
		}
	}

4.分析

Floyd算法核心算法是三重循环，时间复杂度为O(n^3)。

5.源码

https://github.com/chainessss/Algorithm-