Alguem me ajuda por favor!!!!
Uma empresa de aviação está passando por recuperação judicial. Hoje ela opera em 5 (cinco) destinos, mas por causa do processo de recuperação judicial vai diminuir esses destinos. O grafo ilustrado a seguir mostra a operação atual da empresa:
Os vértices 0, 1, 2, 3 e 4 representam as cidades que a companhia opera hoje. O trajeto é representado pelas arestas que liga 0 a 1, 0 a 2, 1 a 3, 1 a 4, e assim por diante. O custo (peso) entre cada conexão está representado por pelos valores nas setas.
Utilizando o algoritmo de Dijkstra, desenvolva um programa em linguagem C que informe o caminho de menor custo saindo de 0 e chegando em 3. O resultado do seu programa deverá indicar os aeroportos que continuarão sendo operados pela companhia.
segue em anexo o percurso.
de ja agradeço!
Soluções para a tarefa
Segue o Algoritmo de Dijkstra
//Bibliotecas
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <locale.h>
//Variáveis
int destino, origem, vertices = 0;
int custo, *custos = NULL;
//Prototipação
void dijkstra(int vertices,int origem,int destino,int *custos);
void menu_mostrar(void);
void grafo_procurar(void);
void grafo_criar(void);
//Função principal
int main(int argc, char **argv) {
setlocale(LC_ALL,"Portuguese");
int opt = -1;
//Laço principal do menu
do { //Desenha o menu na tela
menu_mostrar();
scanf("%d", &opt);
switch (opt) {
case 1:
//cria um novo grafo
grafo_criar();
break;
case 2: //procura os caminhos
if (vertices > 0) {
grafo_procurar();
}
break;
}
} while (opt != 0);
printf("\nAlgoritmo de Dijkstra finalizado...\n\n");
system("pause");
return 0;
}//Implementação do algoritmo de Dijkstra
void dijkstra(int vertices,int origem,int destino,int *custos)
{
int i, v, cont = 0;
int *ant, *tmp;
int *z; /* vertices para os quais se conhece o caminho minimo */
double min;
double dist[vertices]; /* vetor com os custos dos caminhos */
/* aloca as linhas da matriz */
ant = (int*) calloc (vertices, sizeof(int *));
if (ant == NULL) {
system("color fc");
printf ("** Erro: Memória Insuficiente **");
exit(-1);
}
tmp = (int*) calloc (vertices, sizeof(int *));
if (tmp == NULL) {
system("color fc");
printf ("** Erro: Memória Insuficiente **");
exit(-1);
}
z = (int *) calloc (vertices, sizeof(int *));
if (z == NULL) {
system("color fc");
printf ("** Erro: Memória Insuficiente **");
exit(-1);
}
for (i = 0; i < vertices; i++) {
if (custos[(origem - 1) * vertices + i] !=- 1) {
ant[i] = origem - 1;
dist[i] = custos[(origem-1)*vertices+i];
}
else {
ant[i]= -1;
dist[i] = HUGE_VAL;
}
z[i]=0;
}
z[origem-1] = 1;
dist[origem-1] = 0;
/* Laco principal */
do { /* Encontrando o vertice que deve entrar em z */
min = HUGE_VAL;
for (i=0;i<vertices;i++){
if (!z[i]){
if (dist[i]>=0 && dist[i]<min) {
min=dist[i];v=i;
}
}
} /* Calculando as distancias dos novos vizinhos de z */
if (min != HUGE_VAL && v != destino - 1) {
z[v] = 1;
for (i = 0; i < vertices; i++){
if (!z[i]) {
if (custos[v*vertices+i] != -1 && dist[v]
+ custos[v*vertices+i] < dist[i]) {
dist[i] = dist[v] + custos[v*vertices+i];
ant[i] =v;
}
}
}
}
}while (v != destino - 1 && min != HUGE_VAL);
/* Mostra o Resultado da busca */
printf("\tDe %d para %d: \t", origem, destino);
if (min == HUGE_VAL) {
printf("Não Existe\n");
printf("\tCusto: \t- \n");
}
else {
i = destino;
i = ant[i-1];
while (i != -1) {
tmp[cont] = i+1;
cont++;
i = ant[i];
}
for (i = cont; i > 0 ; i--) {
printf("%d -> ", tmp[i-1]);
}
printf("%d", destino);
printf("\n\tCusto: %d\n",(int) dist[destino-1]);
}
}
void grafo_criar(void){
do {
printf("\nInforme o número de vértices (no minimo 3 ): ");
scanf("%d", &vertices);
} while (vertices < 3 );
if (!custos) {
free(custos);
}
custos = (int *) malloc(sizeof(int)*vertices*vertices);
//Se o compilador falhou em alocar espaço na memória
if (custos == NULL) {
system("color fc");
printf ("** Erro: Memória Insuficiente **");
exit(-1);
} //Preenchendo a matriz com -1
for (int i = 0; i <= vertices * vertices; i++){
custos[i] = -1;
}
do {
system("cls");
printf("Entre com as Arestas:\n");
do {
printf("digite a origem (entre 0 e %d ou 00 para sair): ", vertices); // aqui não aceita entrar com aresta inicial zero
scanf("%d", &origem);
} while (origem < 0 || origem > vertices);
if (origem) {
do {
printf("Digite o destino (entre 1 e %d, menos %d): ", vertices, origem);
scanf("%d", &destino);
} while (destino < 1 || destino > vertices || destino == origem);
do {
printf("Digite o custo (positivo) do vértice %d para o vértice %d: ",
origem, destino);
scanf("%d",&custo);
} while (custo < 0);
custos[(origem-1) * vertices + destino - 1] = custo;
}
} while (origem);
}
//Busca os menores caminhos entre os vértices
void grafo_procurar(void){
int i, j;
system("cls");
system("color 03");
printf("Lista dos Menores Caminhos no Grafo Dado: \n");
for (i = 1; i <= vertices; i++) {
for (j = 1; j <= vertices; j++) {
dijkstra(vertices, i,j, custos);
}
printf("\n");
}
system("pause");
system("color 07");
}
//Desenha o menu na tela
void menu_mostrar(void){
system("cls");
printf("Implementação Mapa Estrutura de Dados II, solução com Algoritmo de Dijasktra\n");
printf("Opcoes:\n");
printf("\t 1 - Adicionar um Grafo\n");
printf("\t 2 - Procura Os Menores Caminhos no Grafo\n");
printf("\t 0 - Sair do programa\n");
printf("? ");
}