欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

所有节点对最短路径的Floyd算法:可以有负权边,但不能有负权回路

程序员文章站 2024-03-17 14:52:40
...

Floyd-Warshall算法,中文亦称弗洛伊德算法,是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权(但不可存在负权回路)的最短路径问题。

1、形象的理解:(此部分内容为转载整理)
原文见:彻底弄懂最短路径问题博客第2.2部分。
1.1、Floyd算法的基本思想:
从任意节点A到任意节点B的最短路径不外乎2种可能:

  • 1是直接从A到B;
  • 2是从A经过若干个节点到B。

所以,我们假设dist(AB)为节点A到节点B的最短路径的距离,对于每一个节点K,我们检查dist(AK) + dist(KB) < dist(AB)是否成立,如果成立,证明从A到K再到B的路径比A直接到B的路径短,我们便设置 dist(AB) = dist(AK) + dist(KB),这样一来,当我们遍历完所有节点K,dist(AB)中记录的便是A到B的最短路径的距离。

1.2、错误代码:

for (int i=0; i<n; ++i) {
  for (int j=0; j<n; ++j) {
    for (int k=0; k<n; ++k) {
      if (dist[i][k] + dist[k][j] < dist[i][j] ) {
        dist[i][j] = dist[i][k] + dist[k][j];
      }
    }
  }
}

但是这里我们要注意循环的嵌套顺序,如果把检查所有节点K放在最内层,那么结果将是不正确的,为什么呢?因为这样便过早的把i到j的最短路径确定下来了,而当后面存在更短的路径时,已经不再会更新了。
让我们来看一个例子,看下图:
所有节点对最短路径的Floyd算法:可以有负权边,但不能有负权回路
图中红色的数字代表边的权重。如果我们在最内层检查所有节点K,那么对于A->B,我们只能发现一条路径,就是A->B,路径距离为9,而这显然是不正确的,真实的最短路径是A->D->C->B,路径距离为6。造成错误的原因就是我们把检查所有节点K放在最内层,造成过早的把A到B的最短路径确定下来了,当确定A->B的最短路径时dist(AC)尚未被计算。所以,我们需要改写循环顺序,如下:
ps:个人觉得,这和银行家算法判断安全状态(每种资源去测试所有线程),树状数组更新(更新所有相关项)一样的思想。

1.3、正确代码:

for (int k=0; k<n; ++k) {
  for (int i=0; i<n; ++i) {
    for (int j=0; j<n; ++j) {
            /*
            实际中为防止溢出,往往需要选判断 dist[i][k]和dist[k][j
            都不是Inf ,只要一个是Inf,那么就肯定不必更新。 
            */
      if (dist[i][k] + dist[k][j] < dist[i][j] ) {
        dist[i][j] = dist[i][k] + dist[k][j];
      }
    }
  }
}

1.4、路径保存问题:

void floyd() {
      for(int i=1; i<=n ; i++){
        for(int j=1; j<= n; j++){
          if(map[i][j]==Inf){
               path[i][j] = -1;//表示  i -> j 不通 
          }else{
               path[i][j] = i;// 表示 i -> j 前驱为 i
          }
        }
      }
      for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
          for(int j=1; j<=n; j++) {
            if(!(dist[i][k]==Inf||dist[k][j]==Inf)&&dist[i][j] > dist[i][k] + dist[k][j]) {
              dist[i][j] = dist[i][k] + dist[k][j];
              //path[i][k] = i;//删掉
              path[i][j] = path[k][j];
            }
          }
        }
      }
    }
    void printPath(int from, int to) {
        /*
         * 这是倒序输出,若想正序可放入栈中,然后输出。
         * 
         * 这样的输出为什么正确呢?个人认为用到了最优子结构性质,
         * 即最短路径的子路径仍然是最短路径
         */
        while(path[from][to]!=from) {
            System.out.print(path[from][to] +"");
            to = path[from][to];
        }
    }

2、原理与伪代码:
所有节点对最短路径的Floyd算法:可以有负权边,但不能有负权回路

总结:

1、基于动态规划,代码中把经过的节点k放在最外层测试。
2、Floyd-Warshall算法的时间复杂度为O(N3),空间复杂度为O(N2)。

相关标签: 算法导论笔记