Link para o vídeo: https://youtu.be/DlBCPXbcevM
Código Fonte:
#include <bits/stdc++.h>
#define infinito 9999999
using namespace std;
///implementação da estrutura de dados descrita no arquivo do lab
typedef int vertice;
typedef struct CelAdj CelAdj;
typedef struct Dijkstra_struct Dijkstra_struct;
typedef int* vetor;
typedef vetor* matriz;
struct Dijkstra_struct
{
int** distancia;
int** predecessor;
};
struct CelAdj
{
vertice vert;
int minutos;
CelAdj *prox;
};
struct CelVert
{
char aeroporto[30];
CelAdj *listaAdj;
};
struct digrafo
{
int nvert;
CelVert *vertices;
};
digrafo G;
void Ordenar_listas();
void Memoria()
{
G.vertices = (CelVert*)malloc(G.nvert*sizeof(CelVert));
for(int i = 0; i< G.nvert; i++)
{
G.vertices[i].listaAdj = NULL;
}
}
void Leitura(FILE* arqEntrada)
{
int origem, destino, lig, tempo, rotas_minimas, destino1, destino2;
CelAdj* aux;
fscanf(arqEntrada,"%d ", &G.nvert);
Memoria();
for(int i = 0; i < G.nvert ; i++)
{
fgets(G.vertices[i].aeroporto, 30, arqEntrada);
}
fscanf(arqEntrada,"%d", &lig);
for(int j = 0; j < lig; j++)
{
fscanf(arqEntrada,"%d %d %d", &origem, &destino, &tempo);
aux = G.vertices[origem].listaAdj;
if(aux != NULL)///se já houver alguem ligado ao vertice
{
for(; aux->prox != NULL; aux = aux->prox);
aux->prox = (CelAdj*)malloc(sizeof(CelAdj));
aux = aux->prox;
aux -> vert = destino;
aux -> minutos = tempo;
aux ->prox = NULL;
}
else///se nao houver ninguem ligado ao vertice ainda
{
G.vertices[origem].listaAdj = (CelAdj*)malloc(sizeof(CelAdj));
(G.vertices[origem].listaAdj)->vert = destino;
(G.vertices[origem].listaAdj)->minutos = tempo;
(G.vertices[origem].listaAdj)->prox = NULL;
}
}
///ordenação das listas de adjacência; ta ok!!!
}
void Printar_Grafo(FILE* saida)
{
fprintf(saida,"Digrafo:\n");
for(int i = 0; i < G.nvert; i++)
{
fprintf(saida,"%d (%s):",i, G.vertices[i].aeroporto);
for(CelAdj* aux = G.vertices[i].listaAdj; aux != NULL; aux = aux->prox)
{
if(aux->prox != NULL)
fprintf(saida," %d(%d)", aux->vert, aux -> minutos);
if(aux->prox == NULL)
fprintf(saida," %d(%d)\n", aux->vert, aux -> minutos);
}
}
}
void Ordenar_listas()///ordena as listas de adjacência de cada elemento do vetor de structs
{
for(int i = 0; i < G.nvert; i++)
{
CelAdj* aux;
aux = G.vertices[i].listaAdj;
if(aux->prox == NULL)
{
return;
}
else
{
for(; aux->prox!=NULL; aux = aux->prox)
{
CelAdj* q = NULL;
q = aux->prox;
if(q->prox == NULL)
{
return;
}
else
{
q = aux->prox;
q = q->prox;
aux = aux->prox;
for(; q!=NULL; q = q->prox)
if(q->vert < aux->vert)
{
CelAdj x = *aux;
*aux = *q;
*q = x;
}
}
}
}
}
}
Dijkstra_struct Dijkstra() ///Preenche as matrizes de distancia e de predecessão, aplicando o algoritmo de Dijkstra n vezes
{
Dijkstra_struct grafo;
CelAdj *p;
bool **analisado;
int n = G.nvert, menor;
analisado = (bool**)malloc(n*sizeof(bool*));
grafo.distancia = (matriz)malloc(n*sizeof(vetor));
grafo.predecessor = (matriz)malloc(n*sizeof(vetor));
for(int i = 0; i < n; i++)
{
grafo.distancia[i] = (vetor)malloc(n*sizeof(int));
grafo.predecessor[i] = (vetor)malloc(n*sizeof(int));
analisado[i] = (bool*)malloc(n*sizeof(bool));
}
for(int i = 0; i < n; i++)
{
grafo.distancia[i][i] = 0;
grafo.predecessor[i][i] = i;
analisado[i][i] = false;
for(int j = 0; j < n; j++)
{
if(i != j)
{
grafo.distancia[i][j] = infinito;
grafo.predecessor[i][j] = -1;
analisado[i][j] = false;
}
}
}
for(int i = 0; i < n; i++)
{
for(int t = 0; t < n; t++)
{
int k;
for(k = 0; k < n; k++)
{
if(!analisado[i][k])
{
menor = k;
break;
}
}
for(int j = 0; j < n; j++)
{
if(grafo.distancia[i][j] < grafo.distancia[i][menor] && !analisado[i][j])
menor = j;
}
analisado[i][menor] = true;
for(p = G.vertices[menor].listaAdj; p != NULL; p = p->prox)
{
if(grafo.distancia[i][p->vert] > grafo.distancia[i][menor] + p->minutos)
{
grafo.distancia[i][p->vert] = grafo.distancia[i][menor] + p->minutos;
grafo.predecessor[i][p->vert] = menor;
}
}
}
}
return grafo;
}
void Rota_Minima(FILE* entrada, FILE* saida, Dijkstra_struct grafo, int n)
{
stack<int> pilha;
int rotas, de, para, atual = 0;
fscanf(entrada, "%d", &rotas);
fprintf(saida, "Rotas minimas:\n");
while (rotas > 0)
{
fscanf(entrada, "%d %d", &de, ¶);
fprintf(saida, "%d a %d: ", de, para);
if(grafo.distancia[de][para] < infinito)
{
if(para != de)
{
fprintf(saida, "%d", de);
atual = para;
while(grafo.predecessor[de][atual] != de)
{
pilha.push(atual);
atual = grafo.predecessor[de][atual];
}
pilha.push(atual);
while(!pilha.empty())
{
fprintf(saida, "-%d", pilha.top());
pilha.pop();
}
fprintf(saida, " (%d minutos)\n", grafo.distancia[de][para]);
}
else
fprintf(saida, "(0 minutos)\n");
}
else
fprintf(saida, "sem voos\n");
rotas--;
}
fprintf(saida, "\n");
}
void DFS(int* pai, int *expl, int *comp, int *ce, int *cc, int v, FILE* saida)///auxilia no algoritmo de tarjan para encontrarmos trajetos fechados
{
CelAdj *p;
expl[v] = ++(*ce);
for(p = G.vertices[v].listaAdj; p != NULL; p = p->prox)
{
if(expl[p->vert] == 0)
{
pai[p->vert] = v; /// Armazenamos os pais na árvore de exploração
DFS(pai, expl, comp, ce, cc, p->vert, saida);
}
else if(expl[p->vert] < expl[v] && comp[p->vert] == 0)
{
stack<int> pilha;
int atual = v;
fprintf(saida, "%d", p->vert);
///invertemos a ordem da impressão
while(atual != p->vert)
{
pilha.push(atual);
atual = pai[atual];
}
while(!pilha.empty())
{
fprintf(saida, "-%d", pilha.top());
pilha.pop();
}
fprintf(saida, "-%d\n", p->vert);
}
}
comp[v] = ++(*cc);
}
void ciclos(FILE* saida)
{
int *pai = (vetor)malloc(G.nvert*sizeof(int));
int *expl = (vetor)malloc(G.nvert*sizeof(int));
int *comp = (vetor)malloc(G.nvert*sizeof(int));
int ce = 0, cc = 0;
for(int i = 0; i < G.nvert; i++)
{
expl[i] = 0;
comp[i] = 0;
pai[i] = -1;
}
fprintf(saida, "Trajetos fechados:\n");
for(int i = 0; i < G.nvert; i++)
{
if(expl[i] == 0)
DFS(pai, expl, comp, &ce, &cc, i, saida);
}
}
int main()
{
FILE *entrada, *saida;
entrada = fopen("entrada.txt", "r");
saida = fopen("saida.txt", "w");
Leitura(entrada);
Ordenar_listas();
Dijkstra_struct grafo = Dijkstra();
Printar_Grafo(saida);
Rota_Minima(entrada, saida, grafo, G.nvert);
ciclos(saida);
fclose(entrada);
fclose(saida);
}
