Floyd算法

多源汇最短路。
使用邻接矩阵存储图 d[i,j]
算法实现：
for (k=1;k<=n;k++)
     for (i=1;i<=n;i++) 
         for (j=1;j<=n;j++) 
              d[i,j] = min(d[i,j],d[i,k]+d[k,j]);

循环完之后d[i,j]存的是最短路。
基本原理是动态规划。

可以处理负权，但是不能处理负环。

acwing854