c - Floyd-Warshall 算法无法正确找到最短路径的长度

Question

这可能是一个糟糕的问题，因为我的代表很低，但我已经研究了几个小时的其他解决方案，我的代码似乎与我遇到的工作解决方案几乎相同。请不要忽略基于低代表的问题。

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

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

这是图表的样子:

---

我的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

---

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

---

实现:

#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]);
            }
        }
    }
}

---

测试客户端(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()

Answer 1

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

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

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