C algoritmo de dijksrta's erro

[adriantuler]

boa tarde, estou com um problema no código abaixo, não consigo fazer o mesmo funcionar com algarismos decimais, nas rotas, mas com números inteiros funciona, alguém poderia me ajudar?

 

 

#include <stdio.h>
#define INFINITY 9999
#define MAX 10
void Dijkstra(int Graph[MAX][MAX], int n, int start);

void Dijkstra(int Graph[MAX][MAX], int n, int start) {
  int cost[MAX][MAX], distance[MAX], pred[MAX];
  int visited[MAX], count, mindistance, nextnode, i, j;

  // Creating cost matrix
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      if (Graph[i][j] == 0)
        cost[i][j] = INFINITY;
      else
        cost[i][j] = Graph[i][j];

  for (i = 0; i < n; i++) {
    distance[i] = cost[start][i];
    pred[i] = start;
    visited[i] = 0;
  }

  distance[start] = 0;
  visited[start] = 1;
  count = 1;

  while (count < n - 1) {
    mindistance = INFINITY;

    for (i = 0; i < n; i++)
      if (distance[i] < mindistance && !visited[i]) {
        mindistance = distance[i];
        nextnode = i;
      }

    visited[nextnode] = 1;
    for (i = 0; i < n; i++)
      if (!visited[i])
        if (mindistance + cost[nextnode][i] < distance[i]) {
          distance[i] = mindistance + cost[nextnode][i];
          pred[i] = nextnode;
        }
    count++;
  }

  // Printing the distance
  for (i = 0; i < n; i++)
    if (i != start) {
      printf("\nDistance from source to %d: %d", i, distance[i]);
    }
}
int main() {
  int Graph[MAX][MAX], i, j, n, u;
  n = 5;

  Graph[0][0] = 0;
  Graph[0][1] = 13,192;
  Graph[0][2] = 0;
  Graph[0][3] = 0;
  Graph[0][4] = 0;

  Graph[1][0] = 1;
  Graph[1][1] = 0;
  Graph[1][2] = 0;
  Graph[1][3] = 0;
  Graph[1][4] = 46,172;


  Graph[2][0] = 0;
  Graph[2][1] = 6,596;
  Graph[2][2] = 0;
  Graph[2][3] = 0;
  Graph[2][4] = 32,98;


  Graph[3][0] = 0;
  Graph[3][1] = 0;
  Graph[3][2] = 0;
  Graph[3][3] = 0;
  Graph[3][4] = 0;


  Graph[4][0] = 0;
  Graph[4][1] = 0;
  Graph[4][2] = 0;
  Graph[4][3] = 0;
  Graph[4][4] = 0;



  u = 0;
  Dijkstra(Graph, n, u);

  return 0;
}

 

[devair1010]

@adriantuler @adriantuler    Nesse tóPco  você pode ver sobre esse exercício :

https://www.clubedohardware.com.br/forums/topic/1599078-algoritmo-de-dijkstra/#comment-8406369

[Plástico Bolha]

Acho que as alterações que fiz resolvem, cuidado com o INFINITY, ele estava arredondando os resultados de forma que tirava a exatidão do float durante as somas entre os custos.

#include <stdio.h>

#define INFINITY 9999
#define MAX 10
const float INF = 9999;

void Dijkstra(float Graph[MAX][MAX], int n, int start) {
    float cost[MAX][MAX], distance[MAX], pred[MAX];
    int visited[MAX], count, nextnode, i, j;

    // Creating cost matrix
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            if (Graph[i][j] == 0)
                cost[i][j] = INF;
            else
                cost[i][j] = Graph[i][j];

    for (i = 0; i < n; i++) {
        distance[i] = cost[start][i];
        pred[i] = start;
        visited[i] = 0;
    }

    distance[start] = 0;
    visited[start] = 1;
    count = 1;

    while (count < n - 1) {
        float mindistance = INF;

        for (i = 0; i < n; i++)
            if (distance[i] < mindistance && !visited[i]) {
                mindistance = distance[i];
                nextnode = i;
            }

        visited[nextnode] = 1;
        for (i = 0; i < n; i++)
            if (!visited[i])
                if (mindistance + cost[nextnode][i] < distance[i]) {
                    distance[i] = mindistance + cost[nextnode][i];
                    pred[i] = nextnode;
                }
        count++;
    }

    // Printing the distance
    for (i = 0; i < n; i++)
        if (i != start) {
            printf("\nDistance from source to %d: %f", i, distance[i]);
        }
}

int main() {
    float Graph[MAX][MAX], i, j, n, u;
    n = 5;

    Graph[0][0] = 0;
    Graph[0][1] = 13.192;
    Graph[0][2] = 0;
    Graph[0][3] = 0;
    Graph[0][4] = 0;

    Graph[1][0] = 1;
    Graph[1][1] = 0;
    Graph[1][2] = 0;
    Graph[1][3] = 0;
    Graph[1][4] = 46.172;

    Graph[2][0] = 0;
    Graph[2][1] = 6.596;
    Graph[2][2] = 0;
    Graph[2][3] = 0;
    Graph[2][4] = 32.98;

    Graph[3][0] = 0;
    Graph[3][1] = 0;
    Graph[3][2] = 0;
    Graph[3][3] = 0;
    Graph[3][4] = 0;

    Graph[4][0] = 0;
    Graph[4][1] = 0;
    Graph[4][2] = 0;
    Graph[4][3] = 0;
    Graph[4][4] = 0;

    u = 0;
    Dijkstra(Graph, n, u);

    return 0;
}