《算法导论》笔记（17） 所有结点对最短路径 部分习题

习题25.1-6 O(n^3)时间内从已经计算出的最短路径权重矩阵L计算出前驱矩阵Π。任意的L[i, j]最短路径，若j结点前驱为k，则必然有L[i, j]= L[i, k]+ w[k, j]。如此可遍历L矩阵的第i行所有元素L[i, k]，若L[i, j]= L[i, k]+ w[k, j]，表明k是i-> j最短路径的j的前驱结点。习题25.1-6 O(n^3)时间内从已经计算出的最短路径权重矩阵L计算出前驱矩阵Π。任意的L