数据结构复习(2012).ppt

2. 所有顶点之间的最短路径 Floyd算法的基本思想 定义一个n阶方阵序列 A(0, A(1, , A(n) 其中 A(0) [i][j] = a[i][j] A(k) [i][j] = min { A(k-1)[i][j]A(k-1)[i][k] + A(k-1)[k][j] }, k = 1,2, n A(k) [i][j]是从顶点vi 到vj , 中间顶点的序号不大于k的最短路径 的长度,