Informática, perguntado por devfaculdade, 4 meses atrás

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

Respondido por cadu1197
1

#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]);

}

}

Respondido por sayuriitosilva
0

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

Anexos:
Perguntas interessantes