C程序不启动，执行Dijkstras算法

Question

我正在为 class 做作业，应该以非常具体的方式进行编码。这是目标：

Goal: To implement Dijkstra’s algorithm for single source shortest path problem for a given directed graph using an adjacency matrix representation of the graph.

我正在使用 Makefile 来编译代码。输入将通过 terminal/console ./a7 < datafile 进行。这是输入的示例：

预期输出：

0 2 10
0 3 25
0 1 45
0 4 45
0 5 INF (no path)

代码如下：

#include <limits.h> /* for INT_MAX */
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define N 10 /* max matrix size is 10 x 10 */
#define INF INT_MAX /* infinity? */

int main(int argc, char **argv) {
  void getdata(int amtrx[][N], int *sz, int *stv);
  void dijkstras(int amtrx[][N], int src);

  if (argc < 2) {
    printf("Missing Filename.\n");
    return(1);
  } else if (argc > 2) {
    printf("Too many arguments.\n");
    return(1);
  }
  FILE *f = fopen(argv[1], "r");

  int amtrx[N][N], *sz, *stv;
  stv = malloc(sizeof(int));
  sz = malloc(sizeof(int));
  getdata(amtrx, sz, stv);

  dijkstras(amtrx, *stv);

  fclose(f);
  return(0);
}

void getdata(int amtrx[][N], int *sz, int *stv) {
  int i, j, nsz, nedg, fr, to, vtx, wt;
  scanf("%d %d %d", &nsz, &nedg, &vtx);
  for(i = 0; i < nsz; i++)
    for(j = 0; j < nsz; j++)
      amtrx[i][j] = INF;
  for(i = 0; i < nedg; i++) {
    scanf("%d %d %d", &fr, &to, &wt);
    amtrx[fr][to] = wt;
    amtrx[to][fr] = wt;
  }
  *sz = nsz;
  *stv = vtx;
}

void dijkstras(int amtrx[][N], int src) {
  void printpaths(int amtrx[][N]);
  int mindistance(int dist[], bool sptSet[]);

  int dist[N];
  bool sptSet[N];
  int i, count, v, u;

  for (i = 0; i < N; i++)
    dist[i] = INF, sptSet[i] = false;

  dist[src] = 0;

  for (count = 0; count < N - 1; count++) {
    u = mindistance(dist, sptSet);

    sptSet[u] = true;

    for (v = 0; v < N; v++)
      if (!sptSet[v] && amtrx[u][v] && dist[u] != INF && dist[u] + amtrx[u][v] < dist[v]) {
        dist[v] = dist[u] + amtrx[u][v];
      }
    }
    printpaths(amtrx);
}

int mindistance(int dist[], bool sptSet[]) {
  int min = INF, min_index;
  int v;

  for (v = 0; v < N; v++)
    if (sptSet[v] == false && dist[v] <= min)
      min = dist[v], min_index = v;

  return min_index;
}

void printpaths(int amtrx[N][N]) {
  //to be written
}

到目前为止它只是运行永远不会打印任何东西。我怀疑可能是一个无限循环，但我看不到它在哪里发生。我试图在 GDB 中使用运行，但它只是说 Starting program: /a7 datafile 并且无处可去。我也想帮助确保我的算法是正确的，但如果需要，我可以将其保存到另一个问题。提前致谢！

Answer 1

要在 gdb 的帮助下找出问题所在，您通常需要运行以步进模式编程，以查看挂起或循环的位置和原因。

确保您使用调试符号编译程序（如果您使用的是 gcc 或类似的编译器，则需要 -g 选项）。
为了避免在步进模式下遍历整个程序，您可以在您认为程序挂起时在 gdb 中按 Ctrl-C，然后输入命令 bt。它会告诉你你的程序在哪里。然后你可以输入命令cont，一段时间后中断程序执行，看看你是在不同的地方，还是在同一个...
如果您在第 2 步之后仍然不知道问题的原因是什么，您可以 kill 编程并在您确定为您的程序所在的位置之前设置断点hangs/loops --- 阅读关于 break 的 gdb 文档以了解如何设置断点。

这是 link 在 CMU 托管的 gdb 教程：https://www.cs.cmu.edu/~gilpin/tutorial/

C程序不启动，执行Dijkstras算法

C program doesn't start, implementing Dijkstras algorithm

c

algorithm

dijkstra

adjacency-matrix