Mais um Lab de CES-11! Esta abaixo o código utilizado:

#include<stdio.h>
#include<stdlib.h>

#define infinito 9999

typedef struct caminho caminho;
typedef struct node node;
typedef struct digrafo digrafo;
typedef struct dijkstra dijkstra;

struct dijkstra{
int distancia;
int ordem;
bool check;
};

struct caminho{
int vertice;
int minutos;
caminho *prox;
};

struct node{
char aeroporto[30];
caminho *rota;
};

struct digrafo{
int total;
node vertices[100];//utilizaremos do indice 1 ao m(e nao do 0 ao n-1)
};

void rota_minima(int origem, int chegada, digrafo g, FILE *saida){
int revistados = 0, atual = origem, anterior = origem, proximo;
dijkstra lista[100];
bool conexao = true;
for(int i = 1; i < 100; i++){
lista[i].ordem = lista[i].distancia = infinito;
lista[i].check = false;
}
lista[origem].distancia = 0;
while(revistados < g.total && anterior != atual){
lista[atual].check = true;
caminho *fim;
for(fim = g.vertices[atual].rota, proximo = fim->vertice; fim != NULL; fim = fim->prox){
if(lista[fim->vertice].distancia > lista[atual].distancia + fim->minutos){
lista[fim->vertice].distancia = lista[atual].distancia + fim->minutos;
lista[fim->vertice].ordem = atual;
if(lista[proximo].distancia > lista[fim->vertice].distancia && lista[proximo].check == false)
proximo = fim->vertice;
}
}
anterior = atual;
if(lista[proximo].check == false)
atual = proximo;
revistados++;
}
int resposta[100];
int i;
for(int atual = chegada, i = 0; atual != origem; i++){
if(lista[atual].ordem != infinito){
atual = lista[atual].ordem;
resposta[i] = atual;
}
else{
//printf("Nao existe caminho\n");
conexao = false;
}
}
if(conexao == true){
//fprintf(saida, "%d a %d: %d", origem, chegada, chegada);
for(; i >= 0; i--){
//fprintf(saida, "-%d", resposta[i]);
}
//fprintf(saida, "\n");
}
}

int main(){
digrafo g;///nome do digrafo
FILE *entrada = fopen("entrada.txt", "r");
FILE *saida = fopen("saida.txt", "w");

fscanf(entrada, "%d\n", &g.total);

for(int i = 1; i <= g.total; i++){
//g.vertices[i] = (node*)malloc(sizeof(node));
g.vertices[i].rota = NULL;
fgets(g.vertices[i].aeroporto, 31, entrada);
}//lidos os nomes

int aux;
fscanf(entrada, "%d", &aux);

for(int i = 0; i < aux; i++){
int origem, chegada, tempo;
caminho *fim = g.vertices[origem].rota;
fscanf(entrada, "%d %d %d", &origem, &chegada, &tempo);
if(fim == NULL){
g.vertices[origem].rota = (caminho*)malloc(sizeof(caminho));
g.vertices[origem].rota->minutos = tempo;
g.vertices[origem].rota->vertice = chegada;
g.vertices[origem].rota->prox = NULL;
}
else{
for(; fim->prox != NULL; fim = fim->prox){
}
fim->prox = (caminho*)malloc(sizeof(caminho));
fim->prox->minutos = tempo;
fim->prox->vertice = chegada;
fim->prox->prox = NULL;
}
}//lidas as linhas de voo e alocada a lista de adjacenscias
//falta ordenar a lista

//fprintf(saida, "Digrafo:\n");
for(int i = 1; i <= g.total; i++){
//fprintf(saida, "%d (%s):", (i-1), g.vertices[i]->aeroporto);
caminho *fim = g.vertices[i].rota;
while(fim != NULL){
//fprintf(saida, " %d(%d)", fim->vertice, fim->minutos);
fim = fim->prox;
}
//fprintf(saida, "\n");
}
//fprintf(saida, "\n");//imprimiu o digrafo

fscanf(entrada, "%d", &aux);
//fprintf(saida, "Rotas minimas:\n");
for(int i = 0; i < aux; i++){
int origem, chegada;
fscanf(entrada, "%d %d", &origem, &chegada);
rota_minima(origem, chegada, g, saida);
}//lido todo o documento de entrada
//fprintf(saida, "\n");//imprimiu as rotas minimas

fclose(entrada);
fclose(saida);
return 0;
}