最短路径问题【各顶点间的最短路径——Floyd算法（带权图、无权图）】

文章目录核心思想算法实现注意Floyd 算法弗洛伊德算法 是解决 “多源最短路径” 问题的经典算法。它可以一次性求出图中任意两个顶点之间的最短路径并且允许边权为负值只要图中不含负权回路。核心思想Floyd算法求出每一对顶点之间的最短路径使用动态规划思想将问题的求解分成多个阶段。要更新下一个阶段也就是k这个阶段的矩阵A和矩阵path则需要基于上一个阶段的矩阵A进行条件判断若满足这个条件则对A ,path 对应的位置的值进行修改。对所有的元素都要遍历进行条件判断。算法实现for(intk0;kn;k){// 以 k 作为中转点for(inti0;in;i){// 遍历整个矩阵i为行号j 为列号for(intj0;jn;j){// 公式的代码实现if(A[i][j]A[i][k]A[k][j]){// 以 k 为中转点的路径更短A[i][j]A[i][k]A[k][j];// 更新最短路径长度path[i][j]k;// 记录中间点 k}}}}注意