初级算法-floyd-warshall

问题描述

城市有的之间有路，有的没有，所有信息用矩阵存储。
if 1到2路程为2，那么e[1][2].

image.png

问题解释

解题思路

• 可用n*n深度，或者广度优先搜索.

floyd-warshall

• 计算a到b最短距离，引入第三个点（定点k），通过该定点中转a——k——b、

  
  image.png

则可能缩短，同时我们也可以通过引入两点或者多个点。

• 算法的核心思路是循环遍历。
• 假设任意两点只允许经过1号顶点，只需要判断e[i][1] + e[1][j]是否小于e[i][j].

for(i=1;i<=n;i++)
{
   for(j=1;j<=n;j++)
  {
      if(e[i][j] > e[i][1]+e[1][j])
        e[i][j] = e[i][1] + e[1][j];
  }
}

• 如图可得出3到2,4到2,4到3的路程都变短了。
• 可以得出经过2号会有类似结果。
• 假设允许所有定点作为中转，任意两点最短路程为？

for(k=1;k<=n;k++)
  for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
      if(e[i][j] > e[i][k]+e[k][j])
        e[i][j] = e[i][j] + e[k][j];

image.png

解法floyd-warshall

• 代码

#include <stdio.h>
int main()
{
    int e[10][10],k,i,j,n,m,t1,t2,t3;
    int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值
    //读入n和m，n表示顶点个数，m表示边的条数
    scanf("%d %d",&n,&m);
    
    //初始化
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i==j) e[i][j]=0;  
              else e[i][j]=inf;

    //读入边
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d",&t1,&t2,&t3);
        e[t1][t2]=t3;
    }
    
    //Floyd-Warshall算法核心语句
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(e[i][j]>e[i][k]+e[k][j] ) 
                    e[i][j]=e[i][k]+e[k][j];
    
    //输出最终的结果
    for(i=1;i<=n;i++)
    {
     for(j=1;j<=n;j++)
        {
            printf("%10d",e[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}

• 解释
  如何表示正无穷。我们通常将正无穷定义为99999999，因为这样即使两个正无穷相加，其和仍然不超过int类型的范围（C语言int类型可以存储的最大正整数是2147483647）。

不能解决带有“负权回路”因为带有“负权回路”的图没有最短路。

• 时间复杂度