1

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

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

作为摘录，已经提供了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()
4

2 回答 2

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），修复所有警告，并在问题中指出您的代码编译时不会发出任何警告。

于 2014-06-20T19:49:07.860 回答
0

这是一个完整的解决方案。我使用了@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]);
    }
  }
}

使用以下输入文件：

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

我得到了输出：

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

奇怪的是，当我运行您的代码（如上所示）时，它给了我相同的解决方案 - 尽管第一部分的输出非常清楚地表明它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

实际上，通过memset运算写入矩阵的数字是0x0F0F0F0F，它是252645135十进制的。您可以通过查看以下语法memset来理解为什么会这样：

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

c --这是要设置的值。该值作为 int 传递，但该函数使用unsigned char此值的转换填充内存块。
n --这是要设置为该值的字节数。

并结合 9999 的十六进制表示，即

0x270F

int的“unsigned char转换”是该数字以 256 为模，或最低有效字节。在这种情况下，最低有效字节是0x0F并且是写入（重复）到块中每个字节的值 - 因此值0x0F0F0F0F（在我的机器上，anint是四个字节长）。

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

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

现在你生成你的矩阵

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

并且您将函数签名更改为

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

并打电话给他们

shortestPath(matrix); // etc

为了使一切正常工作，您必须在代码中进行一些其他调整（例如：当您分配的内存少于此值时，您不应该尝试将 INF 分配给 NMAX by 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]);
    }
  }
}
于 2014-06-22T22:06:02.927 回答