C Algoritmo de Dijkstra

Sara Rodrigues21 · 16 de maio de 2022

Uma empresa de delivery de comida solicitou uma aplicação onde o entregador recebe uma solicitação de entrega para realizar. A localização atual do motorista é representada a seguir pelo vértice número 1 (um) e o local de entrega está no vértice de número 5 (cinco).

O grafo acima exibe todas as rotas para alcançar o local de entrega a partir do ponto de partida, que é o restaurante. 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 entregador escolher a melhor decisão de rota, pois devido ao aumento consecutivo do valor do combustível, o entregador quer uma estimativa de qual é a melhor rota até o destino da corrida. Foi feito um levantamento histórico do consumo médio das entregas 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 entregador 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 médio do litro da gasolina nesse momento, na sequência: (1-2), (1-3), (2-4), (2-5), (3-2), (3-5), (4-5).

Desenvolva um programa em linguagem C utilizando 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. Apresente na tela todos as rotas com os seus respectivos pesos. Tire um print da sua tela de forma que pegue todos os destinos.

arfneto · 16 de maio de 2022

E?

não fez nadinha?

não tem qualquer pergunta?

Conhece o algoritmo?

Conhece algo de grafos?

Escreveu muitos programas em C?

Sara Rodrigues21 · 17 de maio de 2022

@arfneto então eu comecei a fazer aqui, só q o professor me confundiu com uma videoaula

agora, Sara Rodrigues21 disse:

@arfneto então eu comecei a fazer aqui, só q o professor me confundiu com uma videoaula

vou te mandar o código q fiz, se você puder me ajudar

@arfneto

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

typedef struct

{

unsigned custo[7]; // pesos dos vertices

const char* filial[5]; // nomes para as filiais

const char* nome;

const char* RA; // mais fácil de testar

} Transp;

Transp* apaga(Transp*);

Transp* cria(const char*, const char*);

int mostra(Transp*);

int main( int argc, char** argv)

{

const char* RA_exemplo = "2025703-5";

char RA[10] = {0};

if (argc < 2)

{ // vai usar o exemplo mesmo

strncpy(RA, RA_exemplo, 7);

}

else

{ // tem 7 ou 6

if (strlen(argv[1]) >= 7)

strncpy(RA, argv[1], 7);

else

{

if (strlen(argv[1]) == 6)

{ // se tem so 6 digitos poe '1' no final

strncpy(RA, argv[1], 6);

RA[6] = '1';

RA[7] = 0;

}

else

strncpy(RA, RA_exemplo, 7);

}

}; // if()

// cria uma transportadora de teste

Transp* teste = cria(RA, "MS Mundo TR");

mostra(teste);

teste = apaga(teste);

return 0;

}

Transp* apaga(Transp* T)

{

free(T);

return NULL;

}

Transp* cria(const char* RA, const char* nome)

{

const char* local[] = {

"Matriz - MS 1",

"Paracatu - MG 2",

"Marquinho - PR 3",

"Belo Horizonte - MG 4",

"Porto de Santos - SP 5",

};

Transp* tr = (Transp*)malloc(sizeof(Transp));

for (int i = 0; i < 5; i += 1) tr->filial[i] = local[i];

printf("RA: \"%s\"\n", RA);

for (int i = 0; i < 7; i += 1) tr->custo[i] = 100 * (RA[i] - '0');

tr->RA = RA;

tr->nome = nome;

return tr;

};

int mostra(Transp* tr)

{

printf("%s\t(RA considerado: '%s')\n\n", tr->nome, tr->RA);

for (int i = 0; i < 5; i += 1) printf(" %d %s\n", 1+i, tr->filial[i]);

printf("\nOs pesos: ");

for (int i = 0; i < 7; i += 1) printf("%c=%d ", 'A' + i, tr->custo[i]);

printf("\n");

return 0;

}

2 minutos atrás, Sara Rodrigues21 disse:

@arfneto então eu comecei a fazer aqui, só q o professor me confundiu com uma videoaula

vou te mandar o código q fiz, se você puder me ajudar

@arfneto

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

typedef struct

{

    unsigned        custo[7]; // pesos dos vertices

    const char*     filial[5]; // nomes para as filiais

    const char*     nome;

    const char*     RA; // mais fácil de testar

}   Transp;

Transp* apaga(Transp*);

Transp* cria(const char*, const char*);

int     mostra(Transp*);

int main( int argc, char** argv)

{

    const char* RA_exemplo = "2025703-5";

    char   RA[10] = {0};

    if (argc < 2)

    {   // vai usar o exemplo mesmo

        strncpy(RA, RA_exemplo, 7);

    }

    else

    {   // tem 7 ou 6

        if (strlen(argv[1]) >= 7)

            strncpy(RA, argv[1], 7);

        else

        {

            if (strlen(argv[1]) == 6)

            {   // se tem so 6 digitos poe '1' no final

                strncpy(RA, argv[1], 6);

                RA[6] = '1';

                RA[7] = 0;

            }

            else

                strncpy(RA, RA_exemplo, 7);

        }

    }; // if()

    // cria uma transportadora de teste

    Transp* teste = cria(RA, "MS Mundo TR");

    mostra(teste);

    teste = apaga(teste);

    return 0;

}

Transp* apaga(Transp* T)

{

    free(T);

    return NULL;

}

Transp* cria(const char* RA, const char* nome)

{

    const char* local[] = {

        "Matriz - MS 1",

        "Paracatu - MG 2",

        "Marquinho - PR 3",

        "Belo Horizonte - MG 4",

        "Porto de Santos - SP 5",

    };

    Transp* tr = (Transp*)malloc(sizeof(Transp));

    for (int i = 0; i < 5; i += 1) tr->filial[i] = local[i];

    printf("RA: \"%s\"\n", RA);

    for (int i = 0; i < 7; i += 1) tr->custo[i] = 100 * (RA[i] - '0');

    tr->RA = RA;

    tr->nome = nome;

    return tr;

};

int         mostra(Transp* tr)

{

    printf("%s\t(RA considerado: '%s')\n\n", tr->nome, tr->RA);

    for (int i = 0; i < 5; i += 1) printf("    %d %s\n", 1+i, tr->filial[i]);

    printf("\nOs pesos: ");

    for (int i = 0; i < 7; i += 1) printf("%c=%d ", 'A' + i, tr->custo[i]);

    printf("\n");

    return 0;

}

só não sei se tá certo

arfneto · 17 de maio de 2022

o código que você fez é uma cópia do código de exemplo que eu postei em 9 de julho do ano passado em

Sugiro ler a discussão toda e escrever de volta

Sara Rodrigues21 · 18 de maio de 2022

23 horas atrás, arfneto disse:

o código que você fez é uma cópia do código de exemplo que eu postei em 9 de julho do ano passado em

Sugiro ler a discussão toda e escrever de volta@arfneto sim sim, eu já li só q não to entendendo nada

me ajuda fazendo favor

arfneto · 18 de maio de 2022

Em 17/05/2022 às 15:20, Sara Rodrigues21 disse:

então eu comecei a fazer aqui, só q o professor me confundiu com uma videoaula

E então o programa que você começou a fazer é o mesmo que eu postei no ano passado, e tem até o mesmo RA que eu usei no exemplo?

Sara Rodrigues21 · 18 de maio de 2022

@arfneto isso mesmo, peguei o seu como base para fazer a atividade até porque o RA é diferente e os números passados também

7 minutos atrás, Sara Rodrigues21 disse:

@arfnetoolha o print q tirei

arfneto · 18 de maio de 2022

26 minutos atrás, Sara Rodrigues21 disse:

isso mesmo, peguei o seu como base para fazer a atividade até porque o RA é diferente e os números passados também

Em 17/05/2022 às 15:20, Sara Rodrigues21 disse:

vou te mandar o código q fiz, se você puder me ajudar

Entendo. Então o código que você fez é o programa que eu postei no ano passado e você não conseguiu nem compilar?

Deve postar o código todo, usando aquele botão code como está explicado no primeiro post do forum.

Podia ter postado ao menos o que tem mas linhas que citou.

Deve imaginar que aquele programa não deixaria de compilar de um ano para outro. Notou as referências a C99? Não estaria usando uma definição da linguagem muito muito antiga?

Que compilador está usando? Que opções está usando para compilar? Deve usar ao menos a versão de 2011 eu acho. Poste o código.

Sara Rodrigues21 · 18 de maio de 2022

@arfneto o programa q eu uso é o codepad

agora, Sara Rodrigues21 disse:

@arfneto o programa q eu uso é o codepad, e a linguagem é em C

agora, Sara Rodrigues21 disse:

@arfneto o programa q eu uso é o codepad

arfneto · 18 de maio de 2022

Não sei o que dizer.

Não postou o código como está agora.

Não conheço esse programa codepad

Não disse que opções está usando para compilar e nem ao menos de está usando uma versão igual ou mais recente que a de 2011.

Sara Rodrigues21 · 18 de maio de 2022

5 minutos atrás, Sara Rodrigues21 disse:

@arfneto o programa q eu uso é o codepad

vou te mandar o código

#include <stdio.h> #include <stdlib.h> #include <math.h> int destino, origem, vertices = 0; int custo, *custos = NULL; void dijkstra(int vertices,int origem,int destino,int *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); printf("\nAlgoritmo de Dijkstra inalizado...\n\n"); system("pause"); return 0; } void dijkstra(int vertices,int origem,int destino,int *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) { system("color fc"); printf ("** Erro: Memória Insuficiente **"); exit(-1); } tmp = (int*) calloc (vertices, sizeof(int *)); if (tmp == NULL) {

agora, Sara Rodrigues21 disse:

vou te mandar o código

#include <stdio.h> #include <stdlib.h> #include <math.h> int destino, origem, vertices = 0; int custo, *custos = NULL; void dijkstra(int vertices,int origem,int destino,int *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); printf("\nAlgoritmo de Dijkstra inalizado...\n\n"); system("pause"); return 0; } void dijkstra(int vertices,int origem,int destino,int *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) { system("color fc"); printf ("** Erro: Memória Insuficiente **"); exit(-1); } tmp = (int*) calloc (vertices, sizeof(int *)); if (tmp == NULL) {

@arfneto ele é um compilador online, a versão é atualizada

te mandei um pedaço do código

@arfneto vou te mostrar no outro compilador, um momento

https://www.onlinegdb.com/online_c_compiler

arfneto · 18 de maio de 2022

2 minutos atrás, Sara Rodrigues21 disse:

ele é um compilador online, a versão é atualizada

te mandei um pedaço do código

fuja disso. Você não tem controle de nada usando esse tipo de programa. O que quer dizer com "a versão é atualizada"? Você pode compilar um código C hoje considerando a linguagem em vários padrões, todos "atualizados", mas precisar estabelecer qual é. A opção -std.

Sobre o código, que imagino que seja simplesmente o programa que eu postei para mostrar algo para alguém no ano passado, vou te pedir de novo: use o botão code como explicado no primeiro post do forum. É só apertar um botão, aquele. E colocar o código DENTRO.

Pouco útil um pedaço do código. Apenas quero saber se mudou algo do programa que eu escrevi.... Se você manda uma parte com o texto todo grudado não vou chegar a nenhuma conclusão.

Sara Rodrigues21 · 18 de maio de 2022

@arfneto ok então, vou arrumar aqui

8 minutos atrás, Sara Rodrigues21 disse:

vou te mandar o código

#include <stdio.h> #include <stdlib.h> #include <math.h> int destino, origem, vertices = 0; int custo, *custos = NULL; void dijkstra(int vertices,int origem,int destino,int *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); printf("\nAlgoritmo de Dijkstra inalizado...\n\n"); system("pause"); return 0; } void dijkstra(int vertices,int origem,int destino,int *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) { system("color fc"); printf ("** Erro: Memória Insuficiente **"); exit(-1); } tmp = (int*) calloc (vertices, sizeof(int *)); if (tmp == NULL) {

@arfneto ele é um compilador online, a versão é atualizada

te mandei um pedaço do código

@arfneto vou te mostrar no outro compilador, um momento

https://www.onlinegdb.com/online_c_compiler

arfneto · 18 de maio de 2022

18 minutos atrás, Sara Rodrigues21 disse:

ele é um compilador online, a versão é atualizada

te mandei um pedaço do código

Não entendeu o que expliquei.... Esqueça esse programa. Se eu entendi sequer se pode saber a versão da linguagem que ele usa.

E com esse outro apareceram coisas na tela?

Não vai postar o código mesmo?

O programa que eu postei certamente não teria um menu. Você colocou isso no programa antes dele estar pronto?

Sugiro esquecer esse codepad

Onde vai ver a versão? As opções?

Esse é do online gdb.

Não ajuda muito também. Mas note que tem 5 versões de C++ e 2 de C.

Não ajuda muito. Prefira algo comum, que possa controlar.

Não tem acesso a um computador? A uma plataforma online de desenvolvimento com compiladores como o gcc ou clang ou o MSVC?

Sara Rodrigues21 · 19 de maio de 2022

@arfneto agora eu tô no caminho?

agora, Sara Rodrigues21 disse:

@arfneto agora eu tô no caminho?

to usando o rextester online

agora, Sara Rodrigues21 disse:

@arfneto agora eu tô no caminho?

to usando o rextester online

peguei seu exemplo pra testar o programa e deu certo

arfneto · 19 de maio de 2022

4 minutos atrás, Sara Rodrigues21 disse:

peguei seu exemplo pra testar o programa e deu certo

bom que o exemplo te ajudou!

Sara Rodrigues21 · 19 de maio de 2022

@arfneto vou escrever novamente aqui, daí te mando para dar uma olhada ok, muito obrigada viu

@arfneto em me tira uma dúvida aqui

nessa parte de custo, o valor q está dentro do colchete é o peso do vértice né?

51 minutos atrás, Sara Rodrigues21 disse:

@arfneto vou escrever novamente aqui, daí te mando para dar uma olhada ok, muito obrigada viu

@arfneto em me tira uma dúvida aqui

nessa parte de custo, o valor q está dentro do colchete é o peso do vértice né? como eu sei qual é o valor pra ser posto, seria referente ao RA do aluno?

Sara Rodrigues21 · 20 de maio de 2022

@arfneto

//Bibliotecas

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

//Variaveis

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){
int opt= -1;

//Laço principla 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,inte 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 if (!z[i]){

if (dist[i]>=0 && dist[i] 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 numero de vertices (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("Origem (entre 1 e %d ou ‘0’ para sair): ", vertices);

scanf("%d", &origem);

} while (origem < 0 || origem > vertices);

if (origem) {

do {

printf("Destino (entre 1 e %d, menos %d): ", vertices,

origem);

scanf("%d", &destino);

} while (destino < 1 || destino > vertices || destino ==

origem);

do {

printf("Custo (positivo) do vertice %d para o vertice %d: ",

origem, destino);

scanf("%d",&custo);

custo *= 6.596;

} 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("Implementacao do Algoritmo de Dijasktra\n");

printf("opções:\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("? ");

}

agora, Sara Rodrigues21 disse:

@arfneto

//Bibliotecas

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

//Variaveis

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){
int opt= -1;

//Laço principla 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,inte 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 if (!z[i]){

if (dist[i]>=0 && dist[i] 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 numero de vertices (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("Origem (entre 1 e %d ou ‘0’ para sair): ", vertices);

scanf("%d", &origem);

} while (origem < 0 || origem > vertices);

if (origem) {

do {

printf("Destino (entre 1 e %d, menos %d): ", vertices,

origem);

scanf("%d", &destino);

} while (destino < 1 || destino > vertices || destino ==

origem);

do {

printf("Custo (positivo) do vertice %d para o vertice %d: ",

origem, destino);

scanf("%d",&custo);

custo *= 6.596;

} 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("Implementacao do Algoritmo de Dijasktra\n");

printf("opções:\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("? ");

}

dá uma olhada fazendo favor e me fala se tá certo?

arfneto · 21 de maio de 2022

Acho que já te falei sobre isso, mas nunca coloque um menu em um programa que não está pronto.

NUNCA escreva um programa interativo se puder evitar. Só vai perder tempo.

Mais sobre o código

use o tal botão code como explicado no primeiro post do forum
estamos falando de um programa que eu escrevi, mas não me lembro do contexto e sequer li o tópico do ano passado

seu programa sequer compila. Por exemplo não pode declarar

    double
        dist[vertices]; /*vetor com os custos dos caminhos*/

não use esses comentários /**/ Isso é um inferno e serve para casos específicos. Prefira sempre //
não use acentos em comentários
inicialize todas as variáveis
teste SEMPRE o retorno de scanf(). é ingênuo seguir sem testar
```
    for (i = 0; i < vertices; i++)
```
declare as variáveis de controle do loop DENTRO do comando. E nunca deixe uma variável com um nome ingênuo como 'i' global na função.
esse algoritmo é bem simples. Procure confirmar o resultado com um caminho conhecido ou um problema que já tenha resposta.

Sobre as coisas que acrescentou

o menu não foi boa ideia agora. E se vai usar um menu entenda que não há sentido em uma função menu que não retorna a opção, que é a coisa mais óbvia que vem depois de mostrar as opções.

    printf("Implementacao do Algoritmo de Dijasktra\n");
    printf("opções:\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("? ");

Eu sempre escrevo isso e tenho uma lista das mesmas coisas que SEMPRE acontecem:

não tem sentido 6 printf() de uma linha ao invés de um printf() de 6 linhas. Vai demorar 50x mais e é o diabo para alinhar e entender o que vai sair na tela. Compare

    printf("\
Implementacao do Algoritmo de Dijasktra\n\
\n\
opções:\n\
\t 1 - Adicionar um Grafo\n\
\t 2 - Procura Os Menores Caminhos no Grafo\n\
\t 0 - Sair do programa\n\
\n\
    ?");

Não misture lógica com formatação ou coleta de dados. NUNCA. É um pesadelo.

Cores, limpar a tela, chamar system() no meio de uma função "grafo_procurar()?"??

    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");

nunca use system(). Para nada. Não estará fazendo nada. Não vai aprender nada. Está programando em C. system() foi escrita em C. O sistema foi escrito em C.

Sara Rodrigues21 · 23 de maio de 2022

@arfneto não tô entendendo mais nada, esse negócio é muito difícil

arfneto · 23 de maio de 2022

1 minuto atrás, Sara Rodrigues21 disse:

não tô entendendo mais nada, esse negócio é muito difícil

é muito vago isso. Está escrevendo em um forum. Pode conseguir muitas respostas mas precisa fazer as perguntas. Escolha algo dessas coisas que não entende e vá perguntando...

Notou que já tem 20 mensagens nesse tópico?

Do que eu te expliquei, por exemplo, o que não entendeu? Nada perguntou.

Sara Rodrigues21 · 25 de maio de 2022

@arfneto

Acho que já te falei sobre isso, mas nunca coloque um menu em um programa que não está pronto.

NUNCA escreva um programa interativo se puder evitar. Só vai perder tempo.

começando por aqui...

arfneto · 25 de maio de 2022

1 hora atrás, Sara Rodrigues21 disse:

começando por aqui...

Não entendi

Sara Rodrigues21 · 25 de maio de 2022

@arfneto sobre começar a escrever o código, não colocar o menu em um programa que não está pronto.

não entendi

arfneto · 25 de maio de 2022

Um programa interativo é uma perda de tempo. Ao colocar o menu você só atrasa o desenvolvimento e os testes. Você escreve as funções e testa com constantes, com arquivos que você digita no IDE com os vértices, com funções que inserem um ou 10 ou 10 mil vértices, com funções factory que retornam grafos, coisas assim.

Quando estiver segura do que escreveu você coloca um menu lá para a tal interação.

Ao ter o menu antes de tudo só fica lento e difícil de testar. Não há sentido em ficar parada adicionando um mesmo grafo 20 vezes porque a lógica do programa ainda não está certa, por exemplo.

Parece que tem uma regra de começar os programas por um menu, a julgar pelo que vejo nos programas posados aqui no forum. E não é uma boa ideia.