又是一年 CSP 复赛，已经一年没写过最短路了，赶紧复习一下。 Floyd-Warshall 算法 Floyd 算法是用来求所有结点对最短路的。适用于所有不含负环的图。 这个算法运用了 DP 的思想。首先定义 f[k][i][j] 表示只允许经过结点 $1, 2, \cdots k$，结点 $i$ 到结点 $j$ 的最短路长度。初始化时，f[k][i][i] = 0，其他赋值为 $+\infty$…
又是一年 CSP 复赛，已经一年没写过最短路了，赶紧复习一下。 Floyd-Warshall 算法 Floyd 算法是用来求所有结点对最短路的。适用于所有不含负环的图。 这个算法运用了 DP 的思想。首先定义 f[k][i][j] 表示只允许经过结点 $1, 2, \cdots k$，结点 $i$ 到结点 $j$ 的最短路长度。初始化时，f[k][i][i] = 0，其他赋值为 $+\infty$…
讨论
登录后参与讨论
还没有评论，来说第一句吧。