floyd算法是一种专门的最短路径算法，时间复杂度O(N^3)，可以算多源，又算负值，比较简单，不错。

他的具体方法——

（1）赋最大值，存特别值。

（2）取中间点，又名中转点。

（3）枚举开头结尾，更新小值——

 a[i][j]=a[i][k]+a[k][j];

（4）做一些小改动，按题来。

中心代码如下：

void floyd()//floyd算法算最短路径

{

  for(int k=1; k<=n; k++)//中转点k

    for(int i=1; i<=n; i++)

      if(i!=k)

        for(int j=1; j<=n; j++)//枚举i、j

          if(i!=j&&j!=k&&a[i][k]+a[k][j]<a[i][j])

            a[i][j]=a[i][k]+a[k][j];//更新最小值

}

典型题目：一本通1342：【例4.1】最短路径问题。

再见 ~~