数据结构课件110章全第七章图幻灯片.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Floyd 算法的求解过程 设 C 为 n 行 n 列的代价矩阵，c[ i, j ] 为 i --- j 的权值。如果 i=j ；那么 c[ i, j ] = 0。如果 i 和 j 之间无有向边；则 c[ i, j ] = ∞ 1、使用 n 行 n 列的矩阵 A 用于计算最短路径。 初始时， A[ i, j ] = c[ i, j ] 2、进行 n 次迭代 在进行第 k 次迭代时，我们将使用如下的公式： Ak-1[ i, j ] Ak[ i, j ] = MIN Ak-1[ i, k ] + Ak-1[ k, j ] 注意：第 k 次迭代时，针对结点 k 进行。原 Ak-1 矩阵的第 k 行，第 k 列保持不变。左上至右下的对角线元素也不 变。 最短路径 2、每一对顶点之间的最短路径：Floyd 算法 V1 V2 加权有向图： 求各结点之间的最短路径 V0 5 3 8 2 j k i Ak-1[ i, k ] Ak-1[ k, j ] Ak-1[ i, j ] 0 8 5 3 0 ∞ ∞ 2 0 0 1 2 0 1 2 右图的代价矩阵 c 最短路径 2、每一对顶点之间的最短路径：Floyd 算法 V1 V2 实例及求解过程: V0 5 3 8 2 Floyd 算法的求解过程 设 C 为 n 行 n 列的代价矩阵，c[ i, j ] 为 i --- j 的权值。如果 i=j ；那么 c[ i, j ] = 0。如果 i 和 j 之间无有向边；则 c[ i, j ] = ∞ 1、使用 n 行 n 列的矩阵 A 用于计算最短路径。 初始时， A[ i, j ] = c[ i, j ] 2、进行 n 次迭代 在进行第 k 次迭代时，我们将使用如下的公式： Ak-1[ i, j ] Ak[ i, j ] = MIN Ak-1[ i, k ] + Ak-1[ k, j ] 注意：第 k 次迭代时，针对结点 k 进行。原 Ak-1 矩阵的第 k 行，第 k 列保持不变。左上至右下的对角线元素也不 变。 0 8 5 3 0 ∞ ∞ 2 0 0 1 2 0 1 2 0 8 5 3 0 ∞ ∞ 2 0 0 8 5 3 0 8 ∞ 2 0 0 7 5 3 0 8 5 2 0 0 8 5 3 0 8 5 2 0 A0 A2 A1 A初值 请看实例 最短路径 2、每一对顶点之间的最短路径：Floyd 算法 算法的程序实现: Floyd 算法的程序的简单描述： int i, j k; // 代表结点 for ( i = 0; i n; i++ ) for ( j = 0; j n; j++ ) A[ i, j ] = C[ i, j ]; for ( i = 0; i n; i++ ) A[ i, i ] = 0; for ( k = 0; k n; k++ ) for ( i = 0; i n; i++ ) for ( j = 0; j n; j++ ) if ( A[ i, k ] + A[ k, j ] A[ i, j ] ) A[ i, j ] = A[ i, k ] + A[ k, j ]; 算法的时间代价: O（n3） 应用范围:无负长度的圈 0 1 ∞ -2 0 2 ∞ ∞ 0 A初值 A0 V0 V1 V2 - 2 1 1 0 1 ∞ -2 -1 0 ∞