estou tentando fazer esse exercicio sobre calculo de caminhos entre cidades, porém estou com problemas, alguém pode ajudar?
arquivo: fila_lig.c
typedef enum boolean {false,true} bool;
typedef struct _RegFila{
TipoDado dado;
struct _RegFila *prox;
} RegFila;
typedef RegFila* Fila;
RegFila *AlocaRegFila(){
RegFila* q;
q = (RegFila*)calloc(1, sizeof(RegFila));
if(q==NULL) exit(-1);
return q;
}
Fila CriaFila(){
Fila p;
p = AlocaRegFila();
p->prox = p;
return p;
}
void LiberaFila(Fila p){
RegFila *q,*t;
q = p->prox;
while(q!=p){
t = q;
q = q->prox;
free(t);
}
free(p);
}
bool FilaVazia(Fila p){
return (p==p->prox);
}
void InsereFila(Fila *p, TipoDado x){
RegFila *q;
q = AlocaRegFila();
q->dado = x;
q->prox = (*p)->prox;
(*p)->prox = q;
*p = q;
}
TipoDado RemoveFila(Fila *p){
RegFila *q,*t;
TipoDado x;
q = (*p)->prox;
if(q==*p) exit(-1); /* Fila Vazia */
t = q->prox;
x = t->dado;
q->prox = t->prox;
if(t==*p) *p = q;
free(t);
return x;
}
/* Numero de cidades consideradas */
#define N 6
void Comprimentos(int A[N][N],
int orig, int C[N]) {
Fila f;
int i,j;
f = CriaFila();
for (i = 0; i < N; i++)
C[i] = INT_MAX;
C[orig] = 0;
InsereFila(&f, orig);
while ( !FilaVazia(f) ) {
i = RemoveFila(&f);
for (j = 0; j < N; j++) {
if (A[i][j] == 1 && C[j] == INT_MAX) {
C[j] = C[i] + 1;
InsereFila(&f, j);
}
}
}
LiberaFila(f);
}
void Caminho(int A[N][N],
int orig,
int dest,
int C[N],
int P[N]) {
Fila f;
int i,j;
f = CriaFila();
for (i = 0; i < N; i++) {
C[i] = INT_MAX;
P[i] = -1;
}
C[orig] = 0;
InsereFila(&f, orig);
while ( !FilaVazia(f) ) {
i = RemoveFila(&f);
if (i == dest) break;
for (j = 0; j < N; j++) {
if (A[i][j] == 1 && C[j] == INT_MAX){
C[j] = C[i] + 1;
P[j] = i;
InsereFila(&f, j);
}
}
}
LiberaFila(f);
}
main ---------------------------
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
/* Numero de cidades consideradas */
#define N 6
/* Para utilizar as funcoes de manipulacao de fila
presentes no arquivo fila_lig.c */
typedef int TipoDado;
#include "fila_lig.c"
/* Inserir nesse ponto o código das demais funções anteriores */
int main() {
/*
A[i][j] indica se existe caminho direto da
cidade i para a cidade j.
*/
int A[N][N] = {{0,0,0,0,0,0},
{0,0,1,0,0,1},
{1,0,0,0,0,0},
{0,0,1,0,0,0},
{0,1,0,0,0,1},
{1,0,0,0,0,0} };
/* C[i] vai armazenar o comprimento minimo de caminho
de uma cidade de origem ate a cidade i */
int C[N];
/* P[i] sera a cidade predecessora de i no
caminho otimo calculado, ou P[i] == -1 se i for
a cidade de origem */
int P[N];
/* Vetor auxiliar temporario */
int T[N];
int i,j;
int orig, dest;
/* Calcula os menores valores de comprimento para
todas cidades a partir de uma cidade de origem
(cidade 4 no exemplo abaixo) */
orig = 4;
Comprimentos(A, orig, C);
/* Imprime os comprimentos calculados: */
for (i = 0; i < N; i++) {
if (C[i] == INT_MAX)
printf(" MAX");
else
printf(" %d", C[i]);
}
printf("\n");
/* Calcula um caminho de comprimento minimo entre uma
cidade de origem e uma cidade de destino fornecidas
(4 e 0 no exemplo) */
dest = 0;
Caminho(A, orig, dest, C, P);
/* Copia as cidades percorridas no sentido inverso
(que é dado pelo mapa de predecessores) no vetor T */
j = 0;
i = dest;
while ( i != -1 ) {
T[j] = i;
j++;
i = P[i];
}
/* Imprime cidades percorridas no sentido correto
de orig para dest */
j--;
for ( ; j >= 0; j--) {
printf(" %d", T[j]);
}
printf("\n");
return 0;
}