C < Algoritmo de Dijkstra >

JoãoPereira01 · 8 de julho de 2021

Uma transportadora especializada em grãos opera nas cinco regiões do Brasil, tendo o porto de Santos como seu destino final. Você pode observar as rotas de operações a partir do grafo a seguir:

O porto de Santos é o vértice indicado pelo número 5 (cinco). As demais regiões são representadas pelos demais vértices que vão de 1 (um) a 4 (quatro).

Você foi convidado a desenvolver uma solução que ajude a empresa em uma tomada de decisão, pois devido ao aumento consecutivo do valor do diesel, a empresa quer uma estimativa de quais os menores custos para continuar operando no porto de Santos. Foi feito um levantamento histórico com o custo médio de operação em cada ponto de origem até o destino final.

No contexto da figura, os vértices 1, 2, 3, 4 e 5 representam, respectivamente as regiões cidades em que a transportadora opera hoje. O trajeto é representado pelas arestas que liga (1 a 2), (1 a 3), (2 a 4), (2 a 5), e assim por diante. O custo 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 100, na sequência: (1-2), (1-3), (2-4), (2-5), (3-2), (3-5), (4-5).

Exemplo:

RA 2025703-5 = Será utilizado os seguintes números do seu RA 2025703

RA 202570-5 = Em caso de 6 dígitos, acrescentar o dígito 1 ao final 2025701

(1-2) = 2 * 100 = 200
(1-3) = 0 * 100 = 0
(2-4) = 2 * 100 = 200
......

Considerando que você precisa desenvolver a solução, utilize o algoritmo de Dijkstra e informe o caminho de menor custo saindo de 1 (que é a matriz da empresa em Mato Grosso do Sul) e chegando em 5. O resultado do seu programa deverá indicar as rotas que poderão ser utilizadas pela companhia 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. Cálcular 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)

Esse foi o modo que eu fiz para a alteração com meu RA:

Nesse código falta transferir o numero do meu RA e adicionar o menor para o maior caminho no final foi essa parte que me deixou mais confuso:

#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) {



   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;



  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] != -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("\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);



  if (custos == NULL) {

 system("color fc");

 printf ("** Erro: Memoria Insuiciente **");

 exit(-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);

 } while (custo < 0);

 custos[(origem-1) * vertices + destino - 1] = custo;

 }

 } while (origem);

}



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

}



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

}

arfneto · 9 de julho de 2021

Não entendi o que deixou você confuso e em que estágio está o programa.

Use o botão code. Formate melhor isso. Está difícil de entender.

Eis seu código do tópico acima, formatado de um jeito comum:

#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) {
    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;
  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] != -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("\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);
  if (custos == NULL) {
    system("color fc");
    printf("** Erro: Memoria Insuiciente **");
    exit(-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);
      } while (custo < 0);
      custos[(origem - 1) * vertices + destino - 1] = custo;
    }
  } while (origem);
}
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");
}
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("? ");
}

Não estudei seu programa, mas tem vários dos problemas/vícios comuns. E estes estão por certo atrasando a conclusão e os testes. Não sei dizer sobre a nota.

Não use:

void menu_mostrar(void);
void grafo_procurar(void);
void grafo_criar(void);

Coisas assim são ruins para o desenvolvimento e a manutenção. void(void) é um buraco negro. Nada entre e nada sai. Uma função assim é como uma calculadora que só opera com os mesmos operandos.

Veja esse exemplo, do seu próprio código:

  do {
    menu_mostrar();
    scanf("%d", &opt);

Se é um menu e serve apenas para orientar a digitação de um valor para opt, porque não retorna opt de menu_mostrar() e pronto? Acha que não seria melhor?

Compare:

    switch ( menu_mostrar() )
    {
      case 1:
...

Não é mais simples? Se precisa mesmo do valor de opt em outras pares do programa pode usar

    switch ( opt = menu_mostrar() )
    {
      case 1:
...

Nunca, mas nunca mesmo, use variáveis globais em C. É um erro para corrigir outro. O outro é o fato de não usar argumentos.

Isso é ruim para a manutenção e é proibido em toda parte, escolas e empresas.

Veja grafo_criar() de seu programa:

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);
  }
  ...

opera com vertices. Tem que ser um argumento. Não um valor externo global que só tem um no programa todo. E o pior: aloca aqui e vai liberar sei lá onde...

Teste o retorno de scanf(): não há sentido em seguir se não leu um vértice por exemplo.

Não use system(). É ruim, proibida em toda parte. Não estará fazendo nada. Apenas chamando system() que foi escrita em C em um programa em C. E para que? mudar uma cor na tela? Use o sistema. Programa isso. Mas programe as cores depois de programar o algoritmo de Dijskstra.
Declare as variáveis de controle de um for DENTRO do for. Acha interessante ter em dijkstra() uma variável global à função com esse nominho? 'i'? Claro que vai dar confusão.

JoãoPereira01 · 9 de julho de 2021

@arfneto Então cara... De fato está confuso mas não tenho culpa do que o meu professor passou como base para fazer o trabalho, mas se ainda tiver dicas uteis para a melhor resolução estou aberto para discussões.

Em 08/07/2021 às 21:08, arfneto disse:

Se é um menu e serve apenas para orientar a digitação de um valor para opt, porque não retorna opt de menu_mostrar() e pronto? Acha que não seria melhor?

Estou tentando fazer uma forma que deixe mais claro o código mesmo que ainda tendo algumas partes que estão fora da minha compreensão, mas mesmo assim vou postar aqui na esperança que alguém possa me ajudar.

Agradeço mesmo assim o esforço que você teve em tentar me ajudar!

arfneto · 9 de julho de 2021

Em 08/07/2021 às 23:49, JoãoPereira01 disse:

De fato está confuso mas não tenho culpa do que o meu professor passou como base para fazer o trabalho, mas se ainda tiver dicas uteis para a melhor resolução estou aberto para discussões.

Não me leve a mal. Só estou tentando ajudar. Sobre as "dicas úteis" possa talvez você considerar:

Em 08/07/2021 às 21:08, arfneto disse:

Teste o retorno de scanf(): não há sentido em seguir se não leu um vértice por exemplo.

Em 08/07/2021 às 21:08, arfneto disse:

Não use system(). É ruim, proibida em toda parte. Não estará fazendo nada. Apenas chamando system() que foi escrita em C em um programa em C. E para que? mudar uma cor na tela? Use o sistema. Programa isso. Mas programe as cores depois de programar o algoritmo de Dijskstra

Em 08/07/2021 às 21:08, arfneto disse:

Declare as variáveis de controle de um for DENTRO do for

Notou que formatei o seu código para ficar mais legível? Serve como "dica"? Notou que eu coloquei o seu código, inalterado, dentro da tal caixa de código e formatado de uma maneira usual?

Compare o seu código do modo como postou

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] != -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);

Com o (seu) código como postei, e dentro da tal caixa de código do forum:

  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] != -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);

Achei também isso podia ajudar e seria mais fácil de entender, algo como uma dica também.

Em 08/07/2021 às 23:49, JoãoPereira01 disse:

Estou tentando fazer uma forma que deixe mais claro o código mesmo que ainda tendo algumas partes que estão fora da minha compreensão, mas mesmo assim vou postar aqui na esperança que alguém possa me ajudar

Notou que eu te mostrei não uma mas duas maneiras alternativas de escrever, nesse caso do menu?

Talvez possa voltar lá e reler o que eu escrevi. E quem sabe recortar o seu código que eu reformatei e implementar as sugestões que deixei lá.

Se incorporar algo do que eu escrevi ao seu código eu talvez possa te ajudar melhor em relação ao algoritmo em si.

Desculpe se deixei má impressão.

Esse é um programa interessante e bem complicado para um iniciante. E incorpora a noção de que o cara já programou outras estruturas de dados, aquelas que vão representar os tais grafos.

Isso sempre é apresentado DEPOIS de terem sido usadas outras estruturas de dados, como listas, conjuntos, árvores e heaps.

Mesmo porque para representar os vértices e implementar os algoritmos é preciso ter uma representação para os grafos. E o mais comum é usar matriz de adjacência ou lista de adjacência. E um caminho comum para implementar esses algoritmos é usar uma árvore ou uma estrutura conhecida como heap.

E porque estou escrevendo isso?

Só para lembrar que para implementar isso é muito mais fácil se puder usar os programas anteriores, onde deve por exemplo ter criado uma lista (que pode usar agora para representar os vértices). E deve ter criado um heap (que pode usar agora para escolher os caminhos mais cursos durante o algoritmo.

Veja uma implementação em C aqui no vivaolinux que começa assim

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 */

igualzinho a que escreveu não é? Ou seu professor é o autor?

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

Veja uma outra comum aqui em GfG em C e outras linguagens, essa melhor e com comentários.

JoãoPereira01 · 9 de julho de 2021

@arfneto Mexi bastante nesse código e tentei colocar o máximo de coisas que você falou nas dicas mas ainda ta faltando parte e eu estou perdido novamente, acho que dá para entender melhor sobre o que se trata o exercício e ficou dessa forma :

#include<stdio.h>

#define QTD 9999

#define MAX 5

void dijkstra(int G[MAX][MAX],int n,int inicial);

int main(){

int i,j,u,l,p;

int G[MAX][MAX];

printf("Sabendo que seu RA é 2110696 digite um digito por vez para ver o menor caminho a seguir:\n");

for(l=0 ;l < MAX; l++){

for( p=0; p< MAX; p++){

G[l][p] = 0;

}

printf("\n");

G[0][1]=200;

G[0][2]=100;

G[1][3]=100;

G[1][4]=0;

G[2][1]=600;

G[2][3]=900;

G[4][3]=600;

for(l=0 ;l < MAX; l++){

for( p=0; p< MAX; p++){

printf("%d,",G[l][p]);

}

printf("\n");

}

printf("\nInforme o número inicial:");

scanf("%d",&u);

dijkstra(G,MAX,u);

return 0;

}

void dijkstra(int G[MAX][MAX],int n,int inicial)

{

int custo[n][n],distancia[n],pred[n];

int visitado[n],cont,distanciamin,proxno,i,j;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if(G[i][j]==-1)

custo[i][j]=QTD;

else

custo[i][j]=G[i][j];

for(i=0;i<n;i++){

distancia[i]=custo[inicial][i];

pred[i]=inicial;

visitado[i]=0;

}

distancia[inicial]=0;

visitado[inicial]=1;

cont=1;

while(cont<n-1){

distanciamin=QTD;

for(i=0;i<n;i++)

if(distancia[i]<distanciamin&&!visitado[i]){

distanciamin=distancia[i];

proxno=i;

}

//verifica se existe melhor caminho atraves do proximo node

visitado[proxno]=1;

for(i=0;i<n;i++){

if(!visitado[i])

if(distanciamin+custo[proxno][i]<distancia[i]){

distancia[i]=distanciamin+custo[proxno][i];

pred[i]=proxno;

}

cont++;

}

//imprime o caminho e a distancia de cada node

for(i=0;i<n;i++)

if(i!=inicial){

printf("\nDistancia do no %d = %d",i,distancia[i]);

printf("\nCaminho = %d",i);

j=i;

do{

j=pred[j];

printf("<-%d",j);

}while(j!=inicial);

}

Não consegui fazer sem o uso das letras pois só sei essa forma de resolver

arfneto · 9 de julho de 2021

Em 09/07/2021 às 16:31, JoãoPereira01 disse:

Não consegui fazer sem o uso das letras pois só sei essa forma de resolver

O que significa?

Em 09/07/2021 às 16:31, JoãoPereira01 disse:

Mexi bastante nesse código e tentei colocar o máximo de coisas que você falou nas dicas mas ainda ta faltando parte e eu estou perdido novamente, acho que dá para entender melhor sobre o que se trata o exercício e ficou dessa forma

Então, voltando ao que eu falei antes:

Em 09/07/2021 às 01:39, arfneto disse:

Notou que formatei o seu código para ficar mais legível? Notou que eu coloquei o seu código, inalterado, dentro da tal caixa de código e formatado de uma maneira usual?

Vou outra vez formatar o seu código e colocar dentro da tal caixa code, com o botão code <> que tem aí na tela...

#include <stdio.h>
#define QTD 9999
#define MAX 5
void dijkstra(int G[MAX][MAX], int n, int inicial);
int main() {
  int i, j, u, l, p;
  int G[MAX][MAX];
  printf("Sabendo que seu RA é 2110696 digite um digito por vez para ver o "
         "menor caminho a seguir:\n");
  for (l = 0; l < MAX; l++) {
    for (p = 0; p < MAX; p++) {
      G[l][p] = 0;
    }
  }
  printf("\n");
  G[0][1] = 200;
  G[0][2] = 100;
  G[1][3] = 100;
  G[1][4] = 0;
  G[2][1] = 600;
  G[2][3] = 900;
  G[4][3] = 600;
  for (l = 0; l < MAX; l++) {
    for (p = 0; p < MAX; p++) {
      printf("%d,", G[l][p]);
    }
    printf("\n");
  }
  printf("\nInforme o número inicial:");
  scanf("%d", &u);
  dijkstra(G, MAX, u);
  return 0;
}
void dijkstra(int G[MAX][MAX], int n, int inicial)
{
  int custo[n][n], distancia[n], pred[n];
  int visitado[n], cont, distanciamin, proxno, i, j;
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      if (G[i][j] == -1)
        custo[i][j] = QTD;
      else
        custo[i][j] = G[i][j];
  for (i = 0; i < n; i++) {
    distancia[i] = custo[inicial][i];
    pred[i] = inicial;
    visitado[i] = 0;
  }
  distancia[inicial] = 0;
  visitado[inicial] = 1;
  cont = 1;
  while (cont < n - 1) {
    distanciamin = QTD;
    for (i = 0; i < n; i++)
      if (distancia[i] < distanciamin && !visitado[i]) {
        distanciamin = distancia[i];
        proxno = i;
      }
    // verifica se existe melhor caminho atraves do proximo node
    visitado[proxno] = 1;
    for (i = 0; i < n; i++) {
      if (!visitado[i])
        if (distanciamin + custo[proxno][i] < distancia[i]) {
          distancia[i] = distanciamin + custo[proxno][i];
          pred[i] = proxno;
        }
    }
    cont++;
  }
  // imprime o caminho e a distancia de cada node
  for (i = 0; i < n; i++)
    if (i != inicial) {
      printf("\nDistancia do no %d = %d", i, distancia[i]);
      printf("\nCaminho = %d", i);
      j = i;
      do {
        j = pred[j];
        printf("<-%d", j);
      } while (j != inicial);
    }
}

Vou ver seu programa a tarde

Mudou o mecanismo de alocação de memória? Não é mais o programa como o do tal Vanderson que está no vivaolinux? Está usando agora uma matriz de adjacência como o do outro programa que mostrei, do GfG?

Continuam alguns dos problemas originais

variáveis de controle do for() devem estar DENTRO do comando
TESTE o retorno de scanf()
não precisa e não deve ler nada por enquanto. Já sabe o grafo que vai usar. E de onde partir
use o próprio programa para testar os pesos com o exemplo que já tem
seria melhor ter uma estrutura para guardar as coisas todas relativas ao grafo
no simples: ou usa uma matriz de adjacência ou usa uma lista de adjacência
não misture o cálculo com a impressão

Esse programa --- e algoritmo --- é bem interessante de escrever aprender.

Em geral os programas de estudo não servem para nada. São bem inúteis e os resultados bem simplistas.

Um programa assim vai te dar um resultado sério de uma coisa que dá trabalho pra fazer em papel, mesmo com experiência na região do mapa por exemplo. Ele pode calcular todos os caminhos de A a B, pode mostrar os caminhos mais curtos e as alteranativas de rota.

Só que:

não é trivial
fica muito difícil se não tiver uma representação do modelo em outras estruturas que em geral aparecem uns capítulos antes do livro de estruturas de dados, em especial set stack, list e heap. Claro, pode fazer sem isso mas com elas fica muito mais fácil.

Você está tentando de fato resolver e entender isso ou apenas adaptar algum exemplo que encontrou na internet?

JoãoPereira01 · 9 de julho de 2021

2 horas atrás, arfneto disse:

com o botão code <> que tem aí na tela...

Ataa ele é o que esta na primeira linha entendi achei que era outro botão desculpa da próxima eu coloco

2 horas atrás, arfneto disse:

O que significa?

Acabei me confundindo em relação a esse tópico de baixo

22 horas atrás, arfneto disse:

Declare as variáveis de controle de um for DENTRO do for. Acha esperto ter em dijkstra() uma variável global à função com esse nominho? 'i'? Claro que vai dar confusão.

Você conseguiria me dar um exemplo sobre isso, de como se faz comparando com o que eu fiz ? Eu conseguiria compreender melhor sou novo nessa área estou aprendendo aos poucos

arfneto · 10 de julho de 2021

Em 09/07/2021 às 16:46, arfneto disse:

Você está tentando de fato resolver e entender isso ou apenas adaptar algum exemplo que encontrou na internet?

Como eu te disse antes acho que esse é um programa bem complicado se você não programou aquelas coisas de que falei antes, em especial heap e lista. ...

Você precisa representar todos os vértices e arestas e colocar por ordem de distância. Se não usar uma boa representação o programa fica muito mais difícil.

Não sei se recebeu de seu professsor ou copiou aquele programa do site vivaolinux de que falei. De todo modo deu azar: é um programa muito ruim. O outro que citei do GfG é um pouco melhor, mas não é assim uma beleza. Claro, é apenas minha opinião...

Em 09/07/2021 às 19:28, JoãoPereira01 disse:

Você conseguiria me dar um exemplo sobre isso, de como se faz comparando com o que eu fiz ? Eu conseguiria compreender melhor sou novo nessa área estou aprendendo aos poucos

Veja esse trecho de seu código

  // imprime o caminho e a distancia de cada node
  for (i = 0; i < n; i++)
    if (i != inicial) {
      printf("\nDistancia do no %d = %d", i, distancia[i]);
      printf("\nCaminho = %d", i);
      j = i;
      do {
        j = pred[j];
        printf("<-%d", j);
      } while (j != inicial);
    }

Essa variável i vem de fora. Está declarada em main(). E j também. Isso é ruim. Qualquer outro lugar que mexa nisso vai zoar tudo e você não tem como controlar. NUNCA faça isso. Mesmo porque é sabiamente proibido em toda parte, escolas e empresas.

Se você declarar essa coisa em dijkstra() ela só vai existir ali dentro então você sabe o que está acontecendo.

Mais ainda: tem alguns tipos de erro que podem acontecer numa função que corrompem o valor de variáveis, então quanto maior for o alcance delas --- se chama scope na literatura --- maior a chance de algo sair errado. E, acredite em mim, sai. Sempre sai.

Compare

  // imprime o caminho e a distancia de cada node
  for (int i = 0; i < n; i++)
    if (i != inicial) {
      printf("\nDistancia do no %d = %d", i, distancia[i]);
      printf("\nCaminho = %d", i);
      int j = i;
      do {
        j = pred[j];
        printf("<-%d", j);
      } while (j != inicial);
    }

Nesse caso i e j são locais e nada tem a ver com outras variáveis i e j espalhadas pelo programa

Note esse loop folclórico:

      do {
        j = pred[j];
        printf("<-%d", j);
      } while (j != inicial);
    }

então se j for diferente de inicial vai rodar uma vez só e rodar o printf(). E se j for igual a inicial?

Sabe o que vai acontecer? Não vai sair nunca e vai encher sua tela até cancelar o programa...

void dijkstra(int G[MAX][MAX], int n, int inicial)
{
  int custo[n][n], distancia[n], pred[n];
  int visitado[n], cont, distanciamin, proxno, i, j;

Isso também não existe em C. Não pode declarar a dimensão como n. Deve usar um valor constante.

void dijkstra(int G[MAX][MAX], int n, int inicial)
{
  int custo[n][n], distancia[n], pred[n];
  int visitado[n], cont, distanciamin, proxno, i, j;

Isso também não existe em C. Não pode declarar a dimensão como n. Deve usar um valor constante.

Vou te mostrar um exemplo de como começar um trem desses de um modo mais controlado. Antes de tudo tem que ter algo para descrever o grafo

Vou te mostrar um EXEMPLO em C.

Antes, uma representação pra começar


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;

Isso seria um mínimo, só pra ter algum sentido. Como eu disse, é preciso criar uma notação para os vértices e arestas, e pode ser mesmo o número do lugar e o custo da viagem.

Como tem o lance de usar RA e tem um exemplo, é mais esperto deixar o micro calcular com o exemplo e conferir depois com o seu RA, ao invés de rabiscar num papel. E é isso o que esse programa faz.

Sabemos que a matriz é em Mato Grosso do Sul e o porto em Santos. Então se pode abrir um mapa e apontar a olho para um desenho parecido dá pra escolher o resto.

É legal quando o algoritmo tem algo além de números.

Eis a saída do programa dj1.c, um possível começo de tudo:

Clube>gcc -o tst -Wall dj1.c
Clube>./tst
RA: "2025703"
MS Mundo TR     (RA considerado: '2025703')

    1  Matriz - MS 1
    2  Paracatu - MG 2
    3  Marquinho - PR 3
    4  Belo Horizonte - MG 4
    5  Porto de Santos - SP 5

Os pesos: A=200 B=0 C=200 D=500 E=700 F=0 G=300
Clube>./tst 2110696
RA: "2110696"
MS Mundo TR     (RA considerado: '2110696')

    1  Matriz - MS 1
    2  Paracatu - MG 2
    3  Marquinho - PR 3
    4  Belo Horizonte - MG 4
    5  Porto de Santos - SP 5

Os pesos: A=200 B=100 C=100 D=0 E=600 F=900 G=600
Clube>

Se você roda só com o nominho ele testa com o RA do enunciado. Ou você digita o que quer usar...

E troque aqueles vértices por letras porque tudo 'x' é inútil.

Olha o desenho, cortesia do Google Earth:

Acho que deu pra entender

Eis o programa completo

#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;
}

Espero que sirva como dica.

JoãoPereira01 · 10 de julho de 2021

Em 09/07/2021 às 21:08, arfneto disse:

Essa variável i vem de fora. Está declarada em main(). E j também. Isso é ruim. Qualquer outro lugar que mexa nisso vai zoar tudo e você não tem como controlar. NUNCA faça isso. Mesmo porque é sabiamente proibido em toda parte, escolas e empresas.

Se você declarar essa coisa em dijkstra() ela só vai existir ali dentro então você sabe o que está acontecendo.

Realmente eu fui ensinado da forma mais complicada e realmente dessa forma dava muitos números aleatórios tive que mexer bastante para sumir isso mas o jeito que você falou facilita muito vou passar a usar somente assim.

Em 09/07/2021 às 21:08, arfneto disse:

Espero que sirva como dica

Me ajudou bastante consegui aprender mais aqui do que com o meu atual professor kkkkkkk

Para o caso de fazer o menor custo para o maior eu teria que usar algo desse tipo para começar a construção ?

Em 09/07/2021 às 21:08, arfneto disse:
Transp* cria(const char* RA, const char* nome)

arfneto · 10 de julho de 2021

Em 09/07/2021 às 23:31, JoãoPereira01 disse:

Para o caso de fazer o menor custo para o maior eu teria que usar algo desse tipo para começar a construção ?

Isso.

Como eu disse antes, as duas maneiras mais comuns de representar isso são a matriz de adjacência e a lista de adjacência.

Em C++ ou java por exemplo fica muito mais fácil, proque se pode usar containers tipo listas ou filas ou pilhas direto na linguagem. MAs em C não tem nada.

Por isso eu disse que em estruturas de dados em C grafos são vistos bem depois dessas estruturas todas e aí o aluno já deve ter programas antigos e noção disso tudo.

Começar do zero com uns vetores é difícil e tosco. Vai dar muito trabalho.

Entendeu o programa que mostrei? Percebeu a vantagem de ter uma referência concreta e algo pra testar e ir refinando a estrutura? E a parada de usar o programa para testar o lance de calcular os custos a partir do RA? A razão de coloca letras nos vértices?

Rode em sua máquina e entenda aquilo.

JoãoPereira01 · 12 de julho de 2021

Em 09/07/2021 às 23:43, arfneto disse:

Entendeu o programa que mostrei? Percebeu a vantagem de ter uma referência concreta e algo pra testar e ir refinando a estrutura? E a parada de usar o programa para testar o lance de calcular os custos a partir do RA? A razão de coloca letras nos vértices?

Sim, eu só fiquei com uma duvida

Transp* menorCaminho();

Eu posso usar o Transp* menorCaminho para descobrir o menor caminho para percorrer ? E o que eu poderia colocar dentro do parenteses ? Sendo que eu vou colocar só código abaixo dele no caso seria esse mas não sei se vou ter que fazer alterações

 for(i=0;i<n;i++)
      if(i!=inicial){
        printf("\nDistancia do no %d = %d",i,distancia[i]);
        printf("\nCaminho = %d",i);

        j=i;
        do{
          j=pred[j];
          printf("<-%d",j);
        }while(j!=inicial);
      }
}

arfneto · 12 de julho de 2021

A saída do programa que eu te mostrei e que você disse que tinha entendido...

RA: "2110696"
MS Mundo TR     (RA considerado: '2110696')

    1  Matriz - MS 1
    2  Paracatu - MG 2
    3  Marquinho - PR 3
    4  Belo Horizonte - MG 4
    5  Porto de Santos - SP 5

Os pesos: A=200 B=100 C=100 D=0 E=600 F=900 G=600
Clube>

E o desenho que eu te mostrei, e que também está pedido no enunciado

Noe que os marcadores 1..5 são os vértices, as letras de A a G são as arestas, os nominhos estão na tabela e as distâncias calculadas a partir dos TA estão na saída do programa.

Por outro lado...

Em 09/07/2021 às 21:08, arfneto disse:

Note esse loop folclórico:

        j=i;
        do{
          j=pred[j];
          printf("<-%d",j);
        }while(j!=inicial);
      }

Em 09/07/2021 às 21:08, arfneto disse:

então se j for diferente de inicial vai rodar uma vez só e rodar o printf(). E se j for igual a inicial?

Sabe o que vai acontecer? Não vai sair nunca e vai encher sua tela até cancelar o programa...

Você não entendeu que:

esse trecho faz a mesma coisa que o programa que te mostrei
esse trecho está errado, em loop, pela razão que te expliquei?

1 hora atrás, JoãoPereira01 disse:

Eu posso usar o Transp* menorCaminho para descobrir o menor caminho para percorrer ? E o que eu poderia colocar dentro do parenteses ? Sendo que eu vou colocar só código abaixo dele no caso seria esse mas não sei se vou ter que fazer alterações

O que você vai colocar entre parênteses é chamado lista de parâmetros, ou argumentos.

Transp era pra ser Transportadora só que seria muito comprido . E é um começo para se acostumar com os dados e começar a representação do problema e dar um resultado objetivo.

O que você quer fazer é usar Transp para montar um grafo, representar o desenho. Pode ser dentro da própria estrutura Transp mas não parece muito legal misturar. Transp descreve sua estrutura, os nomes das filiais e os custos. Daí você cria uma representação abstrata, o tal grafo, e usa o algoritmo para calcular o melhor caminho entre Santos e Campo Grande, no caso do desenho, da Matriz ao Porto.

Se você chamar a tal estrutura de Grafo, aquela criada a partir dos dados da transportadora de grãos descrita em Transp, o algortimo vai retornar o que como resultado? Uma outra Transp? Não, claro que não. Transp é a entrada. E a saída? Lógico que a saída é um caminho, uma Lista tipo B,F indicando que sai de Campo Grande para Marquinho e de Marquinho para Santos...

    Lista*    melhor_caminho( Grafo* modelo);

Mas antes de resolver qual o melhor caminho você vai ter que ter listado TODOS os caminhos do vértice 0, a matriz em Campo Grande, para o vértice 5, o porto em Santos. É o que diz no enunciado.

Com o modelo pronto você pode usar para qualquer mapa. Pode criar um mostrando uns lugares em volta de sua casa, com qualquer número, e a distância em quadras, e usar o mesmo algoritmo para encontrar o melhor caminho entre dois pontos, ou listar todas as maneiras de ir de sua casa até o bar, com as distâncias. E depois seguir o caminho e tomar uma no bar.

Para isso se escreve esse tipo de programa.

JoãoPereira01 · 12 de julho de 2021

3 horas atrás, arfneto disse:

então se j for diferente de inicial vai rodar uma vez só e rodar o printf(). E se j for igual a inicial?

Se eu entendi direito eu posso simplesmente descartar essa parta para não dar o erro ?

3 horas atrás, arfneto disse:

Se você chamar a tal estrutura de Grafo, aquela criada a partir dos dados da transportadora de grãos descrita em Transp, o algortimo vai retornar o que como resultado? Uma outra Transp? Não, claro que não. Transp é a entrada.

Ata você usou somente para resolver o inicio da questão e já que eu vou querer saber o resultado final sendo envolvido outra problemática n tem como usar Trasp.

3 horas atrás, arfneto disse:

Mas antes de resolver qual o melhor caminho você vai ter que ter listado TODOS os caminhos do vértice 0

Você consegue me indicar algum vídeo para eu me aprofundar mais sobre o processo de listagem

arfneto · 12 de julho de 2021

1 hora atrás, JoãoPereira01 disse:

Se eu entendi direito eu posso simplesmente descartar essa parta para não dar o erro ?

 j=i;
        do{
          j=pred[j];
          printf("<-%d",j);
        }while(j!=inicial);
      }

Pela 3a vez, leia isso que escreveu e considere

quando entra no do() vai mostrar j, que é pred[j]
uma linha antes você escreveu j = i
- pra que? se vai atribuir outro valor na linha de baixo?
se j que é pred[j] não for igual a inicial seu programa vai ficar em loop aí, para todo o sempre
se não for vai apenas mostrar aquele valor na tela e seguir adiante: inútil

Pode achar grosseiro de novo, mas entenda que não faz sentido o que escreveu

1 hora atrás, JoãoPereira01 disse:

Ata você usou somente para resolver o inicio da questão e já que eu vou querer saber o resultado final sendo envolvido outra problemática n tem como usar Trasp.

De novo? Leia:

5 horas atrás, arfneto disse:

O que você quer fazer é usar Transp para montar um grafo, representar o desenho. Pode ser dentro da própria estrutura Transp mas não parece muito legal misturar. Transp descreve sua estrutura, os nomes das filiais e os custos. Daí você cria uma representação abstrata, o tal grafo, e usa o algoritmo para calcular o melhor caminho entre Santos e Campo Grande, no caso do desenho, da Matriz ao Porto

Transp é uma estrutura que te mostrei para descrever a transportadora, pegar o RA e calcular os custos. Aí você pega os vértices que estão no mapa que eu te mostrei e as arestas que estão no mapa que eu te mostrei e com os valores que o programa que eu te mostrei calcula monta uma coisa que descreva o grafo.

Como eu já te disse outras vezes há duas maneiras de fazer isso, no geral: matriz de adjacência e lista de adjacência.

O programa que postou inicialmente era o programa postado em https://www.vivaolinux.com.br/script/Algoritmo-de-Dijkstra, um programa ruim e que não vai ajudar muito. Não sei se recebeu de alguém que copiou de lá ou resolveu investir nisso, mas é um programa ruim. O autor lá diz que é bem simples e muito útil, mas eu não achei. Só minha opinião.

O programa que te sugeri ler em https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/ é um exemplo melhor, mas também não é um bom programa. Mas é bem melhor que o acima

Em https://brilliant.org/wiki/dijkstras-short-path-finder/ tem um tutorial que mostra os desenhos de como calcular o caminho mais curto, usando nada mais nada menos que o mesmo grafo de seu enunciado.... E tem um pseudo-código ainda... Mundo pequeno...

Vou escrever de novo:

você pode esquecer o que mostrei
mas pode pegar aquele programa e continuar
já te disse: esse é um programa relativamente complicado. Você não respondeu, mas afinal já programou outras estruturas de dados em C?
- O simples para usar esse algoritmo é usar um vetor de listas com os caminhos e simplesmente ver o mais curto.
- Se você tem aquele seu programa de listas ligadas do mês passado e fez um bom programa pode usar aqui para implementar essas tais listas de caminhos possíveis da matriz ao porto
- Se você programou heap, outra estrutura de dados que se estuda antes dos grafos, pode usar isso para ir pegando as listas do vetor de listas por ordem de comprimento, para não ter que fazer um sort das listas pelo comprimento
- Se você programou árvores, que também se estuda antes de grafos, entenda que qualquer programa de percurso de árvore serve para listas os possíveis caminhos entre 2 pontos no grafo. Só tem que se precaver para não entrar em loop no meio do grafo porque na árvore o nó não aparece duas vezes, nas no grafo aparece porque tem mais de um caminho possível ou não precisaria procurar o mais curto

Se você não fez nenhum desses programas antes vai ter que fazer isso do zero e é muito mais difícil.

JoãoPereira01 · 12 de julho de 2021

55 minutos atrás, arfneto disse:

Transp é uma estrutura que te mostrei para descrever a transportadora, pegar o RA e calcular os custos. Aí você pega os vértices que estão no mapa que eu te mostrei e as arestas que estão no mapa que eu te mostrei e com os valores que o programa que eu te mostrei calcula monta uma coisa que descreva o grafo.

A parte do Transp eu tinha entendido só estou mais enrolado na parte final o meu código ta dando muito erro mesmo que eu faça alterações

57 minutos atrás, arfneto disse:

mas afinal já programou outras estruturas de dados em C?

Sim, mas não foi coisas muito avançadas era coisas mais básicas mas no momento eu só estou precisando para entregar o trabalho ai vou ter mais tempo de ver com calma sabe ? Ai dá tempo de treinar fazendo códigos

Eu poderia usar essa lista como um exemplo ?

// Grafos - Lista de adjacência

#include <iostream>
#include <list>
#include <algorithm> // função find

using namespace std;

class Grafo
{
	int V; // número de vértices
	list<int> *adj; // ponteiro para um array contendo as listas de adjacências

public:
	Grafo(int V); // construtor
	void adicionarAresta(int v1, int v2); // adiciona uma aresta no grafo

	// obtém o grau de saída de um dado vértice
	// grau de saída é o número de arcos que saem de "v"
	int obterGrauDeSaida(int v);

	bool existeVizinho(int v1, int v2); // verifica se v2 é vizinho de v1
};

Grafo::Grafo(int V)
{
	this->V = V; // atribui o número de vértices
	adj = new list<int>[V]; // cria as listas
}

void Grafo::adicionarAresta(int v1, int v2)
{
	// adiciona vértice v2 à lista de vértices adjacentes de v1
	adj[v1].push_back(v2);
}

int Grafo::obterGrauDeSaida(int v)
{
	// basta retornar o tamanho da lista que é a quantidade de vizinhos
	return adj[v].size();
}

bool Grafo::existeVizinho(int v1, int v2)
{
	if(find(adj[v1].begin(), adj[v1].end(), v2) != adj[v1].end())
		return true;
	return false;
}

int main()
{
	// criando um grafo de 4 vértices
	Grafo grafo(4);

	// adicionando as arestas
	grafo.adicionarAresta(0, 1);
	grafo.adicionarAresta(0, 3);
	grafo.adicionarAresta(1, 2);
	grafo.adicionarAresta(3, 1);
	grafo.adicionarAresta(3, 2);

	// mostrando os graus de saída
	cout << "Grau de saida do vertice 1: " << grafo.obterGrauDeSaida(1);
	cout << "\nGrau de saida do vertice 3: " << grafo.obterGrauDeSaida(3);

	// verifica se existe vizinhos
	if(grafo.existeVizinho(0, 1))
		cout << "\n\n1 eh vizinho de 0\n";
	else
		cout << "\n\n1 não eh vizinho de 0\n";

	if(grafo.existeVizinho(0, 2))
		cout << "2 eh vizinho de 0\n";
	else
		cout << "2 não eh vizinho de 0\n";

	return 0;
}

arfneto · 13 de julho de 2021

Em 12/07/2021 às 19:18, JoãoPereira01 disse:

Sim, mas não foi coisas muito avançadas era coisas mais básicas mas no momento eu só estou precisando para entregar o trabalho ai vou ter mais tempo de ver com calma sabe ? Ai dá tempo de treinar fazendo códigos

Eu poderia usar essa lista como um exemplo ?

Entenda que são as coisas menos avançadas: estruturas de dados que você já estudou e programou e que se fez algo razoável poderia usar aqui, do modo como te expliquei acima, mais de uma vez.

A maneira comum de implementar um grafo é a que te expliquei, usando listas de adjacências e um vetor de listas com os caminhos e tal. Não vou mais repetir.

Se você não fez e não vai fazer isso--- programar as estruturas de suporte --- vai ter muito trabalho para programar o grafo. Só isso.

é como apertar parafusos com a faca de serra...

Em 12/07/2021 às 19:18, JoãoPereira01 disse:

Eu poderia usar essa lista como um exemplo ?

Sim, claro. É exatamente isso.

E te mostra o que estou tentando te explicar:

class Grafo
{
	int V; // número de vértices
	list<int> *adj; // ponteiro para um array contendo as listas de adjacências

public:
	Grafo(int V); // construtor

Esse também não é assim um programa muito bom, mas serve. Pelo jeito está difícil de achar bons exemplos.

O adequado seria usar um vetor de listas. É muito mais fácil. E não um ponteiro.

O que é adj no exemplo?

É um ponteiro para uma lista de int

Só que C++ tem listas, vetores, mapas, conjuntos, pilhas, filas de prioridade, o diabo. Tudo pronto para você usar: é só declarar. Mas você está programando em C.

Esse é o ponto que tento te explicar: por isso deve programar com atenção essas coisas, não achando que vai entregar o exercício de pilha e o de listas e o de vetor e esquecer para sempre. Se você puder usar as listas que programou no "mês passado" e as pilhas e tal, vai programar um grafo com tranquilidade.

Não dá pra começar de novo a cada programa. Esse é o ponto. Até dá, mas dá um trabalho do 1nf3rn0, como está vendo...

Estruturas de dados são ferramentas para construir programas. É muito mais fácil começar por elas do que começar por uns vetores e uns if e for

De todo modo a primeira coisa é escrever um modelo do grafo, saindo dos dados que tirou de Transp, a estrutura que descreve a transportadora.

Eis um exemplo que pode funcionar, em C. Claro que em C++ é muito mais fácil.


typedef struct
{
    char* nome; // o rotulo do node

}   Vertice;

typedef struct
{
    int     de; // origem A: #vertice
    int     para; // destino B: #vertice
    int     peso; // custo de A para B

}   Aresta;

typedef struct
{   
    int         n_arestas; // vertices em uso
    Aresta*     ar; // vetor de arestas
    int         n_vertices; // nodes em uso
    Vertice*    pt; // vetor de vertices

}   Grafo;