Реализация алгоритма Дейкстры в C дает неправильный (но почти правильный) вывод

Question

Я пытаюсь реализовать алгоритм Дейкстры в c, и у меня почти правильный вывод. Что-то происходит с массивом dist. Он дает очень большие и маленькие цифры.

Ссылка на сайт Я основываю большую часть своего кода алгоритма на: https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/, это также объясняет алгоритм, если вы не знакомы.

Вот код:

#include <limits.h>
#include <stdio.h>
#include<stdbool.h>
#define N 10 /* max matrix size is 10 x 10 */
#define INF INT_MAX /* infinity? */
int src; /* global */

void getdata(int amtrx[3][N], int *n, int *src) {
  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;
  }
  *n = nsz;
  *src = vtx;
}

void printpaths(int dist[], int n) {
  int i;
  for (i = 0; i < n; i++)
    if(i == src);
    else if (dist[i] < INF) {
      printf("%d  %d  %d\n", src, i, amtrx[i]);
    } else {
      printf("%d  %d  INF (no path)\n", src, i);
    }
}

void dijkstras(int amtrx[][N], int n) {
  int dist[n], v;
  bool spt[n];
  int min = INF, u;

  for (v = 0; v < n; v++)
    if (spt[v] == false && dist[v] <= min) {
      min = dist[v], u = v;
      spt[u] = true;
    }

  for (v = 0; v < n; v++)
    if (!spt[v] && amtrx[u][v] != INF && dist[u] != INF && dist[u] + amtrx[u][v] < dist[v])
      dist[v] = dist[u] + amtrx[u][v];

  printpaths(dist, n);
}

int main()  {
  int amtrx[N][N];
  int n;

  getdata(amtrx, &n, &src);
  dijkstras(amtrx, n);
  return 0;
}

Вот вход:

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  1  32701
0  2  -1996178040
0  3  -1996178014
0  4  -1996178044
0  5  32765

Ожидаемый результат:

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

Спасибо за помощь заранее! Я надеюсь, что это просто простое исправление, которое я не вижу:)

update

Я думаю, что алгоритм был неправильным, и я немного поработал над ним, вывод все еще неправильно, но я думаю, что это больше правильно, чем раньше:

void dijkstras(int amtrx[][N], int n) {
  int dist[n], v, q;
  bool spt[n];
  int min = INF, u;

  for (v = 0; v < n; v++) {
    dist[v] = INF;
    spt[v] = false;
  }

  dist[n] = 0;

  for (v = 0; v < n - 1; v++) {
    for (q = 0; q < n; q++) {
      if (spt[v] == false && dist[v] <= min) {
        min = dist[v], u = v;
      }
      spt[u] = true;
    }

    for (v = 0; v < n; v++)
      if (!spt[v] && amtrx[u][v] != INF && dist[u] != INF && dist[u] + amtrx[u][v] < dist[v])
        dist[v] = dist[u] + amtrx[u][v];
  }

  printpaths(dist, n);
}

Вывод сейчас:

0  1  INF (no path)
0  2  INF (no path)
0  3  INF (no path)
0  4  INF (no path)
0  5  INF (no path)

обновление 2

void dijkstras(int amtrx[][N], int n) {
    int min = INF, dist[N], count, v, u;
    bool spt[N];

    for (v = 0; v < N; v++) {
        dist[v] = INF;
    spt[v] = false;
  }

    dist[src] = 0;

    for (count = 0; count < N - 1; count++) {
      for (v = 0; v < N; v++)
        if (spt[v] == false && dist[v] <= min)
            min = dist[v], u = v;

      spt[u] = true;

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

  printpaths(dist, n);
}

вывод :

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

Я так близко, что могу попробовать! Любая помощь приветствуется!

Answer 1

void dijkstras(int amtrx[][N], int n) {
    int min = INF, dist[n], count, v, u;
    bool spt[n];

    for (v = 0; v < n; v++) {
        dist[v] = INF;
    spt[v] = false;
  }

    dist[src] = 0;

    for (count = 0; count < n - 1; count++) {
            min=INF;
      for (v = 0; v < n; v++)
        if (spt[v] == false && dist[v] <= min)
            min = dist[v], u = v;

      spt[u] = true;

      for (v = 0; v < n; v++)
        if (!spt[v] && amtrx[u][v] != INF && dist[u] != INF && dist[u] + amtrx[u][v] < dist[v])
            dist[v] = dist[u] + amtrx[u][v];
    }

  printpaths(dist, n);
}