Um motorista de aplicativo recebeu uma corrida para realizar. A localização atual do motorista é representada a seguir pelo vértice número 1 (um) e a corrida está no vértice de número 5 (cinco).
O grafo acima exibe todas as rotas para alcançar o destino a partir do ponto de partida. O destino da corrida é o vértice indicado pelo número 5 (cinco). As possíveis rotas são representadas pelos demais vértices que vão de 1 (um), que é a origem, a 4 (quatro).
Desenvolva um algoritmo que ajude o motorista de aplicativo a tomar a melhor decisão de rota, pois devido ao aumento consecutivo do valor do combustível, o motorista quer uma estimativa de qual é a melhor rota até o destino da corrida. Para isso, foi feito um levantamento histórico do consumo médio das viagens passando por cada ponto de origem até o destino final.
Na figura do grafo, os vértices 1, 2, 3, 4 e 5 representam, respectivamente as rotas em que o motorista deve passar para chegar ao destino. O trajeto é representado pelas arestas que liga (1 a 2), (1 a 3), (2 a 4), (2 a 5), e assim por diante. O consumo médio (peso) entre cada conexão está representado por X. Você deve substituir o X pelos 7 primeiros dígitos do seu RA (indo da esquerda para direita) multiplicado por 6,596, que é o valor do litro da gasolina nesse momento, na sequência: (1-2), (1-3), (2-4), (2-5), (3-2), (3-5), (4-5).
Exemplo:
RA 2045703-5 = Será utilizado os seguintes números do seu RA 2045703
RA 204570-5 = Em caso de 6 dígitos, acrescentar o dígito 1 ao final 2045701
(1-2) = 2 * 6,596 = 13,192
(1-3) = 0 * 6,596 = 0
(2-4) = 4 * 6,596 = 26,384
......
Utilize o algoritmo de Dijkstra para resolver o problema e informe o caminho de menor custo saindo de 1 (que é o ponto de partida da corrida) e chegando em 5 (que é o destino da corrida). O resultado do seu programa deverá indicar as rotas que poderão ser utilizadas pelo motorista e o seu respectivo peso.
Passos para realizar o Mapa:
1. Desenvolva um programa em linguagem C, salvar com a extensão (.c) que informe os caminhos saindo de 1 e chegando em 5.
1.1. Neste código, usuário deverá excetuar as seguintes ações:
- informar o número de vértices (ponto de rota),
- informar as arestas com suas respectivas rotas de origem e destino,
- informar o custo correspondente ao seu RA para todas as rotas.
1.2. Calcular rotas.
1.3. Apresentar na tela todos os destinos com os seus respectivos pesos.
2. Após a impressão (item 1.3) tirar um print da sua tela de forma que pegue todos os destinos.
- Neste print marque o(s) caminho(s) de menor custo saindo de 1 e chegando em 5 (usar qualquer programa de edição de imagem)
- Salve com extensão (.doc), (.docx), (.pdf), (.png) e (.jpg)
* Indicação de IDE para desenvolver sua atividade MAPA (DEV C++, Code::Block, https://replit.com/)
Soluções para a tarefa
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
int destino, origem, vertices = 0;
float custo;
float *custos = NULL;
void dijkstra(int vertices, int origem, int destino, float *custos);
void menu_mostrar(void);
void grafo_procurar(void);
void grafo_criar(void);
int main(int argc, char **argv) {
int opt = -1;
do {
menu_mostrar();
scanf("%d", &opt);
switch (opt) {
case 1:
grafo_criar();
break;
case 2:
if (vertices > 0) {
grafo_procurar();
}
break;
}
} while (opt != 0);
return 0;
}
void menu_mostrar(void) {
printf("Algoritmo Dijkstra \n");
printf("\t Opcoes:\n");
printf("\t 1-Adicionar um grafo\n");
printf("\t 2-Procurar menores caminhos no grafo\n");
printf("\t 3-Sair do programa\n");
}
void grafo_criar(void) {
do {
printf("informe a quantidade de vertices:");
scanf("%d", &vertices);
} while (vertices < 3);
if (!custos) {
free(custos) ;
} custos = (float*)malloc(sizeof(float) *vertices*vertices);
if (custos == NULL) {
printf("+++ERRO+++");
exit(-1);
}
for (int i = 0; i <= vertices*vertices; i++) {
custos[i] = -1;
}
do {
system("clear");
printf("Entre com as arestas:\n");
do {
printf("Origem(entre 1 e %d ou'0' para sair)",vertices);
scanf("%d", &origem);
} while (origem < 0 || origem > vertices);
if (origem) {
do {
printf("destino(entre1 %d,menos %d)", vertices, origem);
scanf("%d", &destino);
} while (destino < 1 || destino > vertices || destino == origem);
do {
printf("custo(positivo)do vertice %d para vertice %d:", origem,destino);
scanf("%f", &custo);
} while (custos < 0);
custos[(origem - 1) * vertices + destino - 1] = custo;
}
} while (origem);
}
void grafo_procurar(void) {
int i, j;
system("clear");
printf("Menores caminhos do grafo:\n");
for (i = 1; i <= vertices; i++) {
for(j=1;j<=vertices;j++){
dijkstra(vertices, i, j,custos) ;
}
}
}
void dijkstra(int vertices, int origem, int destino, float *custos) {
int i, v, cont = 0;
int *ant, *tmp;
int *z;
double min;
double dist[vertices];
ant = (int*)calloc(vertices, sizeof(int*));
if (ant == NULL) {
printf("ERRO");
exit(-1);
}
tmp = (int*)calloc(vertices, sizeof(int*));
if (tmp == NULL) {
printf("ERRO");
exit(-1);
}
z = (int*)calloc(vertices, sizeof(int*));
if (z == NULL) {
printf("ERRO");
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;
do {
min = HUGE_VAL;
for (i = 0; i < vertices; i++) {
if (!z[i]) {
if (dist[i] >= 0 && dist[i] < min) {
min = dist[i]; v = i;
}
}
}
if (min != HUGE_VAL && v != destino - 1) {
z[v] = 1;
for (i = 0; i < vertices; i++) {
if (!z[i]) {
if (custos[v*vertices + i] !=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);
printf("\t De %d para %d:\t", origem, destino);
if (min == HUGE_VALL) {
printf("não existe\n");
printf("\t custo\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;%.3lf\n",dist[destino-1]);
}
}
De acordo com os conceitos de programação, pode-se afirmar que realizando o programa correto, temos que:
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
int destino, origem, vertices = 0;
float custo;
float *custos = NULL;
void dijkstra(int vertices, int origem, int destino, float *custos);
void menu_mostrar(void);
void grafo_procurar(void);
void grafo_criar(void);
int main(int argc, char **argv) {
int opt = -1;
do {
menu_mostrar();
scanf("%d", &opt);
switch (opt) {
case 1:
grafo_criar();
break;
case 2:
if (vertices > 0) {
grafo_procurar();
}
break;
}
} while (opt != 0);
return 0;
}
void menu_mostrar(void) {
printf("Algoritmo Dijkstra \n");
printf("\t Opcoes:\n");
printf("\t 1-Adicionar um grafo\n");
printf("\t 2-Procurar menores caminhos no grafo\n");
printf("\t 3-Sair do programa\n");
}
void grafo_criar(void) {
do {
printf("informe a quantidade de vertices:");
scanf("%d", &vertices);
} while (vertices < 3);
if (!custos) {
free(custos) ;
} custos = (float*)malloc(sizeof(float) *vertices*vertices);
if (custos == NULL) {
printf("+++ERRO+++");
exit(-1);
}
for (int i = 0; i <= vertices*vertices; i++) {
custos[i] = -1;
}
do {
system("clear");
printf("Entre com as arestas:\n");
do {
printf("Origem(entre 1 e %d ou'0' para sair)",vertices);
scanf("%d", &origem);
} while (origem < 0 || origem > vertices);
if (origem) {
do {
printf("destino(entre1 %d,menos %d)", vertices, origem);
scanf("%d", &destino);
} while (destino < 1 || destino > vertices || destino == origem);
do {
printf("custo(positivo)do vertice %d para vertice %d:", origem,destino);
scanf("%f", &custo);
} while (custos < 0);
custos[(origem - 1) * vertices + destino - 1] = custo;
}
} while (origem);
}
void grafo_procurar(void) {
int i, j;
system("clear");
printf("Menores caminhos do grafo:\n");
for (i = 1; i <= vertices; i++) {
for(j=1;j<=vertices;j++){
dijkstra(vertices, i, j,custos) ;
}
}
}
void dijkstra(int vertices, int origem, int destino, float *custos) {
int i, v, cont = 0;
int *ant, *tmp;
int *z;
double min;
double dist[vertices];
ant = (int*)calloc(vertices, sizeof(int*));
if (ant == NULL) {
printf("ERRO");
exit(-1);
}
tmp = (int*)calloc(vertices, sizeof(int*));
if (tmp == NULL) {
printf("ERRO");
exit(-1);
}
z = (int*)calloc(vertices, sizeof(int*));
if (z == NULL) {
printf("ERRO");
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;
do {
min = HUGE_VAL;
for (i = 0; i < vertices; i++) {
if (!z[i]) {
if (dist[i] >= 0 && dist[i] < min) {
min = dist[i]; v = i;
}
}
}
if (min != HUGE_VAL && v != destino - 1) {
z[v] = 1;
for (i = 0; i < vertices; i++) {
if (!z[i]) {
if (custos[v*vertices + i] !=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);
printf("\t De %d para %d:\t", origem, destino);
if (min == HUGE_VALL) {
printf("não existe\n");
printf("\t custo\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;%.3lf\n",dist[destino-1]);
}
}
O que é programação?
A programação é um processo de escrita, teste e manutenção de um programa de computadores. Ademais, o programa é escrito um uma linguagem de programação para que a máquina entenda o que está sendo pedido, e vale lembrar que diferentes partes de um programa pode ser escrita com diferentes linguagens de programação.
Saiba mais sobre programação em:
brainly.com.br/tarefa/20790680
#SPJ2