C программа не запускается, реализует алгоритм Дейкстры - PullRequest
Новая
       46

C программа не запускается, реализует алгоритм Дейкстры

0 голосов
/ 21 апреля 2020

Я делаю задание для класса, который должен быть закодирован очень специфичным c способом. Вот цель:

Цель: реализовать алгоритм Дейкстры для задачи кратчайшего пути из одного источника для данного ориентированного графа, используя представление матрицы смежности графа.

I Я использую Makefile для компиляции кода. Вход будет принят через терминал / консоль ./a7 < datafile. Вот пример ввода: 

6 11 0
0 1 50
0 2 10
0 4 45
1 2 15
1 4 10
2 0 20
2 3 15
3 1 20
3 4 35
4 3 30
5 4 03

И ожидаемый вывод: 

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
}

Пока он просто работает навсегда и ничего не печатает. Я подозреваю, что, возможно, бесконечное число oop, но я не вижу, где это происходит. Я пытался запустить в GDB, и он просто говорит Starting program: /a7 datafile и не идет никуда. Я также хотел бы помочь убедиться, что мой алгоритм правильный, но я могу сохранить его для другого вопроса, если это будет необходимо. Заранее спасибо!

1 Ответ

2 голосов
/ 22 апреля 2020

Чтобы выяснить, что не так с помощью GDB, вам обычно нужно запустить программу в пошаговом режиме, чтобы увидеть, где и почему она зависает или зацикливается.

  1. Убедитесь, что вы скомпилировали вашу программу с отладочными символами (если вы используете g cc или подобный компилятор, тогда необходима опция -g).
  2. Чтобы избежать обхода всей программы в пошаговом режиме, вы можете просто нажать Ctrl- C в gdb в тот момент, когда вы думаю, что ваша программа зависла, а затем введите команду bt. Он покажет вам, где ваша программа. Затем вы можете ввести команду cont и через некоторое время прервать выполнение программы, чтобы увидеть, находитесь ли вы в другом месте или в том же месте ...
  3. Если вы все еще не знаете, в чем причина Ваша проблема после шага 2, вы можете kill запрограммировать и установить точку останова до места, которое вы определили как место, в котором ваша программа зависает / зацикливается --- прочтите документацию gdb о break, чтобы узнать, как настроить точка останова.

Вот ссылка на учебник GDB, размещенный в CMU: https://www.cs.cmu.edu/~gilpin/tutorial/

...