Floyd-Warshall算法不能正确地找到最短路径的长度

This is probably a bad question to ask on SO since my rep is so low, but I have been looking through other solutions for hours, and my code seems nearly identical to the working solutions that I've come across. Please do not ignore the question based on low rep.

这可能是一个不好的问题，因为我的代表很低，但是我已经花了几个小时寻找其他的解决方案，我的代码看起来和我遇到的工作解决方案几乎是一样的。请不要忽略基于low rep的问题。

The output matrix, d[][] contains the (incorrect) lengths of the shortest paths between a given pair of vertices. The solution provided in the networkx library for Python has been used.

输出矩阵d[][]包含给定顶点对之间最短路径的(不正确的)长度。使用了networkx库中为Python提供的解决方案。

As an excerpt, the results for n=20 have been provided. I'm not printing out the paths greater than infinity (i.e. 99999), since there is overflow.

作为摘录，我们提供了n=20的结果。我没有打印大于无穷大的路径(即99999)，因为存在溢出。

This is what the graph looks like:

这个图是这样的:

---

My Floyd-Warshall algorithm implementation (C)

我的Floyd-Warshall算法实现(C)

20  0   2
20  1   6
20  2   9
20  3   9
20  4   8
20  5   10
20  7   2
20  8   7
20  9   10
20  11  5
20  12  2
20  13  7
20  14  6
20  15  17
20  17  4
20  18  5

---

Networkx solution to Floyd-Warshall algorithm (Python)

Floyd-Warshall算法的Networkx解决方案(Python)

20  0   2
20  1   5
20  2   4
20  3   4
20  4   3
20  5   7
20  7   2
20  8   2
20  9   4
20  11  4
20  12  2
20  13  6
20  14  5
20  15  4
20  17  3
20  18  4
20  20  0

---

Implementation:

实现:

#include <time.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h> 
#include <limits.h>

#define INF 9999
#define min(a,b) (a>b)?b:a;

int n;
/*
* Method signatures
*/
void shortestPath(int matrix[][n]);

int main(){
    char buf[16], c;
    int i, j, weight, ret;

    /* Open file handler for file containing test data */
    FILE *file = fopen("eg2.txt", "r");
    if(file==NULL){
        puts("I/O error: cannot read input file");
        fclose(file);
        exit(1);
    }
    /* Get number of vertices in file */
    fscanf(file, "%d", &n);

    /* Initialise matrix of n*3 elements */
    int matrix[n][n];
    memset(matrix, INF, n*n*sizeof(int));

    while((ret = fscanf(file, "%d %d %d", &i, &j, &weight)) != EOF) {
        if(ret == 3){
            matrix[i][j]=weight;
        } else {
            printf("ERROR: retrieved %d values (expecting 3)\n", ret);
            break;
        }
    }
    fclose(file);

    /* Output matrix */
    for(i=0; i<n; i++){
        matrix[i][i]=0;
        for(j=0; j<n; j++){
            printf("%d  ", matrix[i][j]);
        }
        printf("\n");
    }
    shortestPath(matrix);
}
/*
* Implementation of the Floyd-Warshall path finding algorithm
*/
void shortestPath(int matrix[][n]){
    int d[n][n], k, i, j;

    /* Copy values from matrix[][] to d[][] */
    for(i=0; i<n; i++){
        for(j=0; j<n; j++){
            d[i][j] = matrix[i][j];
        }
    }
    for(k=0; k<n; k++){
        for(i=0; i<n; i++){
            for(j=0; j<n; j++){
                if (d[i][k] + d[k][j] < d[i][j]){
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
    for(i=0; i<n; i++){
        for(j=0; j<n; j++){
            if((d[i][j]!=0)&&(d[i][j]<INF)){
                printf("%d\t%d\t%d\n", i, j, d[i][j]);
            }
        }
    }
}

---

Test client (Python)

测试客户端(Python)

#!/usr/bin/python2.7
try:
    import matplotlib.pyplot as plt
    from collections import defaultdict
    import networkx as nx
    import numpy as np
except:
    raise

nodes = defaultdict(dict)
with open('eg2.txt', 'r') as infile:
    for line in infile.readlines()[1:]:
        line = map(int, line.split())
        src = line[0]
        dst = line[1]
        weight = line[2] 
        nodes[src][dst]=weight

G = nx.Graph()

for i in nodes:
    for j in nodes[i]:
        G.add_edge(i, j, weight=nodes[i][j])

rs = nx.floyd_warshall(G)
for i in rs:
    for j in rs[i]:
        print "%d\t%d\t%d" % (i, j, rs[i][j])

pos = nx.shell_layout(G)
nx.draw(G, pos, node_size=500, node_color='orange', edge_color='blue', width=1)

plt.axis('off')
plt.show()

2 个解决方案

#1

Here is a complete solution for you. I used @pts's suggestion of using a fixed array, and the suggestion from the comments of initializing the array explicitly with a pair of nested loops. I also took some liberties with the way the algorithm works - for example, with the option to have either directed or undirected graphs - and show how you can include some intermediate outputs to help in the debugging.

这里有一个完整的解决方案。我使用了@pts使用固定数组的建议，以及使用一对嵌套循环对数组进行显式初始化的建议。我还对算法的工作方式进行了一些修改——例如，可以选择直接或无向图——并展示如何在调试中包含一些中间输出。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INF 9999
#define MIN(a,b)((a)<(b))?(a):(b)
// uncomment the next line to make processing symmetrical
// i.e. undirected edges
// #define SYM

#define NMAX 20
int n;

void shortestPath(int m[NMAX][NMAX]);
void printMatrix(int m[NMAX][NMAX]);

// implementation of floyd-warshall algorithm
// with minimal error checking
// input file = series of nodes on graph in form
// start, end, length
// algorithm attempts to find shortest path between any connected nodes
// by repeatedly looking for an intermediate node that shortens the current distance
// graphs are directional - 3 4 5 does not imply 4 3 5
// this can be changed by uncommenting the #define SYM line above
// also, hard coded to have no more than 20 nodes - defined with NMAX above
// path to input file is hard coded as "eg2.txt"

int main(void) {
  int i, j, weight, ret;

// open input file:
  FILE *fp = fopen("eg2.txt", "r");
  if(fp == NULL) {
    printf("cannot read input file\n");
    exit(1);
  }
// read number of nodes in the graph:
  fscanf(fp, "%d", &n);
  if(n > NMAX) {
    printf("input too large\n");
    fclose(fp);
    exit(1);
  }
  printf("n is %d\n", n);

// generate matrix:
  int matrix[NMAX][NMAX];
  for(i=0; i<NMAX;i++)
    for(j=0; j<NMAX; j++)
      matrix[i][j] = INF;

  while( (ret = fscanf(fp, "%d %d %d", &i, &j, &weight)) != EOF) {
    if(ret == 3) {
      matrix[i][j] = weight;
#ifdef SYM
      matrix[j][i] = weight;
#endif
    }
  else printf("error reading input\n");
  }
  fclose(fp);

  printMatrix(matrix);
  shortestPath(matrix);
  printMatrix(matrix);

}
void printMatrix(int m[NMAX][NMAX]) {
  int i, j;
  for(i=0; i<n; i++) {
    for(j=0; j<n; j++) {
      if(m[i][j]==INF) printf("  - "); else printf("%3d ", m[i][j]);
    }
    printf("\n");
  }

}

void shortestPath(int d[NMAX][NMAX]) {
  int i, j, k, temp;
  // no need to make a copy of the matrix: operate on the original
  for(k=0; k<n; k++) {
    for(i=0; i<n-1; i++) {
      for(j=0; j<n; j++) {
        if(i==j) continue; // don't look for a path to yourself...
        if(d[i][k] == INF || d[k][j]==INF) continue; // no path if either edge does not exist
        if((temp = d[i][k] + d[k][j]) < d[i][j]) {
          d[i][j] = temp;
#ifdef SYM
          d[j][i] = temp;
#endif
          printf("from %d to %d is shorter via %d: %d + %d is %d\n", i, j, k, d[i][k], d[k][j], temp);
        }
      }
    }
  }
  for(i=0; i<n; i++) {
    for(j=0; j<n; j++) {
      if(d[i][j] < INF) printf("%2d %2d %3d\n", i, j, d[i][j]);
    }
  }
}

With the following input file:

输入文件如下:

5
1 2 3
2 4 2
1 4 8
0 3 7
3 1 2
1 4 2
1 3 1
0 1 1

I got as output:

我作为输出:

n is 5
  -   1   -   7   - 
  -   -   3   1   2 
  -   -   -   -   2 
  -   2   -   -   - 
  -   -   -   -   - 
from 0 to 2 is shorter via 1: 1 + 3 is 4
from 0 to 3 is shorter via 1: 1 + 1 is 2
from 0 to 4 is shorter via 1: 1 + 2 is 3
from 3 to 2 is shorter via 1: 2 + 3 is 5
from 3 to 4 is shorter via 1: 2 + 2 is 4
 0  1   1
 0  2   4
 0  3   2
 0  4   3
 1  2   3
 1  3   1
 1  4   2
 2  4   2
 3  1   2
 3  2   5
 3  4   4
  -   1   4   2   3 
  -   -   3   1   2 
  -   -   -   -   2 
  -   2   5   -   4 
  -   -   -   -   - 

Oddly enough, when I ran your code (as posted above) it gave me the same solution - although the output for the first part made it very clear that the memset wasn't working as you expected:

奇怪的是，当我运行您的代码(如上所述)时，它给了我相同的解决方案——尽管第一部分的输出非常清楚地表明，memset并不像您预期的那样工作:

0  1  252645135  7  252645135  
252645135  0  3  1  2  
252645135  252645135  0  252645135  2  
252645135  2  252645135  0  252645135  
252645135  252645135  252645135  252645135  0  
0   1   1
0   2   4
0   3   2
0   4   3
1   2   3
1   3   1
1   4   2
2   4   2
3   1   2
3   2   5
3   4   4

In fact, the number that is being written to the matrix with the memset operation is 0x0F0F0F0F, which is 252645135 in decimal. You can understand why this is so by looking at the syntax of memset:

实际上，通过memset操作被写入到矩阵的数字是0x0f0f0f0f0f0f，十进制是252645135。通过研究memset的语法，你可以理解为什么会这样:

void *memset(void *str, int c, size_t n)
Parameters
str -- This is pointer to the block of memory to fill.

void *memset(void *str, int c, size_t n)参数str——这是要填充的内存块的指针。

c -- This is the value to be set. The value is passed as an int, but the function fills the block of memory using the unsigned char conversion of this value.
n -- This is the number of bytes to be set to the value.

c——这是要设置的值，值作为int类型传递，但函数使用该值的无符号字符转换填充内存块。n——这是要设置为值的字节数。

and combining with the hexadecimal representation of 9999, which is

结合9999的十六进制表示，也就是

0x270F

The "unsigned char conversion" of an int is that number modulo 256, or the least significant byte. In this case, the least significant byte is 0x0F and that is the value that gets written (repeatedly) to every byte in the block - hence the value 0x0F0F0F0F (on my machine, an int is four bytes long).

int的“无符号字符转换”是数字模块256，或者是最不重要的字节。在这种情况下，最不重要的字节是0x0F，它是块中每个字节(重复地)被写入的值——因此值是0x0f0f0f0f0f(在我的机器上，int是4字节长)。

Afterword
Finally - if you want to use "any size of array", you can add the following couple of functions to your program - and replace the function signatures as indicated. This is a "tricky" way to create a two D array of variable size in C - essentially, when C comes across a pointer of the type int** it will dereference twice. By making this pointer-to-a-pointer point to a block of pointers to the block of memory, you create in effect a 2D array that the compiler can understand.

后记最后-如果你想使用“任意大小的数组”，你可以在你的程序中添加以下几个函数-并替换如所示的函数签名。这是在C中创建一个可变大小的二维数组的一种“技巧”方式——本质上，当C遇到int**类型的指针时，它将取消两次引用。通过将指针指向指针指向内存块的指针块，您实际上创建了编译器可以理解的2D数组。

int **make2D(int r, int c) {
  int ii, **M;
  M = malloc(r * sizeof(int*) );
  M[0] = malloc( r * c * sizeof(int) );
  for(ii=1; ii<r; ii++) M[ii] = M[0] + ii * c * sizeof(int);
  return M;
}

void free2D(int** M) {
  free(M[0]);
  free(M);
}

Now you generate your matrix with

现在你生成你的矩阵

int **matrix;
matrix = make2D(n, n);

and you change the function signatures to

你把函数签名改成

void shortestPath(int **m);
void printMatrix(int **m);

And call them with

和叫他们

shortestPath(matrix); // etc

To make everything work properly you have to make a few other adjustments in your code (example: you should not try to assign INF to all elements of a NMAX by NMAX array when you allocated less memory than that). You can try to figure this out for yourself - but just in case, here is the complete code. One other change I made - I got rid of n as a global variable and made it local to main (and passed it to the various routines that needed it). This is usually a good practice - it's all too easy to mix things up with globals, so use them only when you really have no choice.

为了使一切正常工作，您必须在代码中做一些其他的调整(示例:当您分配的内存少于这个时，您不应该尝试将INF分配给NMAX的所有元素)。您可以试着自己解决这个问题——但是，这里是完整的代码。我还做了另一个更改——我去掉了n作为全局变量，将它本地化到main(并将它传递给需要它的各种例程)。这通常是一个很好的实践——把事情和全局变量混淆在一起太容易了，所以只有在你别无选择的时候才使用它们。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INF 9999
#define MIN(a,b)((a)<(b))?(a):(b)
// uncomment the next line to make processing symmetrical
// i.e. undirected edges
// #define SYM

void shortestPath(int **m, int n);
void printMatrix(int **m, int n);

// create 2D matrix of arbitrary (variable) size
// using standard C:
int **make2D(int r, int c) {
  int ii, **M;
  M = malloc(r * sizeof(int*) );
  M[0] = malloc( r * c * sizeof(int) );
  for(ii=1; ii<r; ii++) M[ii] = M[0] + ii * c * sizeof(int);
  return M;
}

void free2D(int** M) {
  free(M[0]);
  free(M);
}

// implementation of floyd-warshall algorithm
// with minimal error checking
// input file = series of nodes on graph in form
// start, end, length
// algorithm attempts to find shortest path between any connected nodes
// by repeatedly looking for an intermediate node that shortens the current distance
// graphs are directional - 3 4 5 does not imply 4 3 5
// this can be changed by uncommenting the #define SYM line above
// also, hard coded to have no more than 20 nodes - defined with NMAX above
// path to input file is hard coded as "eg2.txt"

int main(void) {
  int i, j, n, weight, ret;

// open input file:
  FILE *fp = fopen("eg2.txt", "r");
  if(fp == NULL) {
    printf("cannot read input file\n");
    exit(1);
  }
// read number of nodes in the graph:
  fscanf(fp, "%d", &n);
  printf("n is %d\n", n);

// generate matrix:
  int **matrix;
// allocate memory:
  matrix = make2D(n, n);
// fill all elements with INF:
  for(i=0; i<n;i++)
    for(j=0; j<n; j++)
      matrix[i][j] = INF;

// read the input file:
  while( (ret = fscanf(fp, "%d %d %d", &i, &j, &weight)) != EOF) {
    if(ret == 3) {
      matrix[i][j] = weight;
#ifdef SYM
// if undirected edges, put in both paths:
      matrix[j][i] = weight;
#endif
    }
  else printf("error reading input\n");
  }
  fclose(fp);

  printMatrix(matrix, n);
  shortestPath(matrix, n);
  printMatrix(matrix, n);

}
void printMatrix(int **m, int n) {
  int i, j;
  for(i=0; i<n; i++) {
    for(j=0; j<n; j++) {
      if(m[i][j]==INF) printf("  - "); else printf("%3d ", m[i][j]);
    }
    printf("\n");
  }

}

void shortestPath(int **d, int n) {
  int i, j, k, temp;
  // no need to make a copy of the matrix: operate on the original
  for(k=0; k<n; k++) {
    for(i=0; i<n-1; i++) {
      for(j=0; j<n; j++) {
        if(i==j) continue; // don't look for a path to yourself...
        if(d[i][k] == INF || d[k][j]==INF) continue; // no path if either edge does not exist
        if((temp = d[i][k] + d[k][j]) < d[i][j]) {
          d[i][j] = temp;
#ifdef SYM
          d[j][i] = temp;
#endif
          printf("from %d to %d is shorter via %d: %d + %d is %d\n", i, j, k, d[i][k], d[k][j], temp);
        }
      }
    }
  }
  for(i=0; i<n; i++) {
    for(j=0; j<n; j++) {
      if(d[i][j] < INF) printf("%2d %2d %3d\n", i, j, d[i][j]);
    }
  }
}

#2

Don't use dynamically sized arrays (e.g. non-constant n in the array size), they may not work the way you think. One simple way to fix your code:

不要使用动态大小的数组(例如，数组大小中的非常量n)，它们可能不会按照您的想法工作。修复代码的一个简单方法是:

#define MAXN 100
int n;
...
  int matrix[MAXN][MAXN];
  scanf("%d", &n);
  if (n < 1 || n > MAXN) abort();
...
void shortestPath(int matrix[][MAXN]) {

Please recompile your code with all warnings enabled (e.g. gcc -W -Wall -Wextra -ansi), fix all the warnings, and indicate in the question that your code compiles without emitting any warning.

请重新编译您的代码，并启用所有警告(例如gcc -W -Wall -Wextra -ansi)，修复所有警告，并在问题中表明您的代码编译时没有发出任何警告。