Floyd算法 概念 Floyd算法，也称为Floyd-Warshall算法，是一种用于求解图中所有顶点对之间最短路径的算法。 它是一种动态规划算法，适用于有向图或带权图，可以处理负权边（但不能包含负权回路，负权回路会导致无限小路径）。 伪代码 12345for(k : V) for(i : V) for(j : V) if(d(i, k) + d(k, j) < d(i, j)) d(i, j) = d(i, k) + d(k, j) 算法过程 该算法的本质是动态规划，以状态转移方程的形式描述如下，其中 dp[k][i][j] 表示 经过前 k 个顶点的松弛，得到的顶点 i 到顶点 j 的最短路径长度 。注意第一维的 k 表示 k 个顶点，第二维和第三维表示具体的顶点。 定义: dp[k][i][j] 表示经过前 k 个顶点的松弛，得到的顶点 i 到顶点 j 的最短路径长度。 边界: dp[0][i][j] = i == j ? 0 : (g[i][j] == 0 ? Inf : g[i][j]) 递推: dp[k][i][j] = min& ...