只有五行的算法----Floyd-Warshall

上图为一个城市地图，图中有4个城市，8条公路 ，公路上的数字表示这条公路的长短，并且这些公路是单向的，我们现在要求出任意两个城市之间的最短路径，也就是求任意两点的最短路径。

我们用一个数据结构来存储图的信息，我们仍然可以用一个4*4的矩阵来存储，比如 1 号城市 到 2 号城市的路程为 2 ，a[1][2] = 2 ，无法到达用无穷的 来表示 ，并且我们约定自己到自己的城市的路程为0 。

当当当当，上面就是初始化好的图结构， 好 ，现在回到问题，我们应该怎样求任意两点之间的最短距离呢，当然我们可以用深搜，广搜求出。可是还有没有其他办法呢。

当然有了，根据以往的经验，如果让任意两个点之间的距离变短，只能引入第三个点（顶点 k），并通过这个顶点k'作为中转才能达到缩短顶点a到达顶点b的目的。

代码如下：

#include <iostream>
#include <cstdio>
using namespace std ;
const int MAX = 1000 ;
const int INF = 0x3f3f3f3f ;
// 只有五行的Floyd - Warshall 算法  -- 最短路径 ;
int a[MAX][MAX];
int n , m ;

int main()
{
  int i , j ,k;
  /* 用一个 n*n的 二维数组来存储图  */
  cin>>n>>m ;
  for ( i= 1 ;i<=n ;i++)
  {
    for(j = 1 ;j<=n ;j++)
    {
      if(i==j)
      a[i][j] = 0 ;
      else
      a[i][j] = INF ;
    }
    
  }
  // 核心算法
  for(i=1;i<=m;i++)
  {
    int t1,t2,t3 ;
    cin>>t1>>t2 >>t3;
    a[t1][t2] = t3 ;
    
  }
  for(k=1;k<=n;k++)
  {
    for(i=1;i<=n;i++)
    {
      for(j=1;j<=n;j++)
      {
        if(a[i][j]>a[i][k]+a[k][j] )
        a[i][j] = a[i][k]+a[k][j];
      }
    }
    
    
  }
  for(i=1;i<=n;i++)
  {
    for(j=1;j<=n;j++)
    {
      printf("%5d",a[i][j]);
    }
    
    printf("\n");
  }
  

  return 0 ;
}