Graph图论Floyed算法(任意两点之间的最短路)可以解决存在负边缘的情况，也可以判断是否存在负循环。
对于最短路，我们首先接触的都是单源的最短路径，即求出起点固定、从点到其他点的最短路径。 但是，如果我们想要求出任意两点之间的最短路径，那么对于所有的点都必须再进行一次dijkstra吗？ 如果明显比较麻烦，难以保存信息，请使用Floyed算法。
在此，我们将使用dp数组dp[ i ][ j ]。 从I到j所需的最短距离，实际上即使考虑数组的作用来理解算法，大部分也可以完成。 那么，假设有点k，从I到j有两种情况。 一个在最短路径上经过k到达j时，另一个不经过k时，动态转移方程可以很好地写出来。
DP[I][j]=min(DP[I][j]，dp[i][k] dp[k][j]
考虑动态数组和动态转移方程，只剩下初始化。 如果我们知道a-b的路程是C，因为最初我们有一条直路，那么初始化时dp[a][b]=c；其他不能直行的初始化为INF，即dp[a][d]=INF； 从自己到自己的距离为0，即dp[i][i]=0；
Floyed算法类似于Bellman_Ford，可以解决负边缘权重的问题，并且只需要检查dp[i][j]是否为负边缘以确定图中是否存在负循环。
完整的代码如下所示。
# include iostream # includecstringusingnamespacestd； 长龙DP [ 10001 ] [ 10001 ]； voidfloyed(intn ) for ) intk=1； k=n； k ) for(intI=1； i=n； I ) for(intj=1； j=n； j ) ) DP[I][j]=min(DP[I][j]，dp[i][k] dp[k][j] )； }}}}int main () {int n，m； cin n m； memset(DP，0x7f7f7f7f，sizeof ) DP )； for(intI=1； i=n； I ) {dp[i][i]=0； }for(intI=0； im； I ) {int a，b； 龙龙c； cin a b c； dp[a][b]=min(dp[a][b]，c )； }for(intI=1； i=n； I ) for(intj=1； j=n； j({coutDP[I][j] ' )； }cout endl； ) Floyed(n； for(intI=1； i=n； I ) for(intj=1； j=n； j({coutDP[I][j] ' )； }cout endl； }返回0； }