Pesquisar na Comunidade

Boa noite gente, eu estou com uma SUPER dúvida... Estou no primeiro período do curso de CC, iniciante em C e ainda não aprendi nada de grafos, árvore binária e etc... mas minha professora passou um TP pra gente que eu já passei dias tentando entender e fazer mas não consegui... Ele consiste em: "Implemente um algoritmo que seja capaz de encontrar o maior caminho entre dois nós inicio e fim de um grafo valorado, isto é, um grafo sem direção que possui um peso no arco para indicar a distância ou custo entre os nós. O algoritmo receberá como parâmetros os nós (inicio e fim), além de uma matriz custo de números inteiros que representa o grafo, denominada matriz de custo, e deverá retornar a maior distância entre os nós informados. A distância entre dois nós é o somatório das distâncias individuais entre os nós intermediários contidos no caminho que liga os nós inicio e fim. A matriz de custo é interpretada como segue. O algoritmo poderá manipular quaisquer outras estruturas de dados (variáveis, vetores, matrizes, registros, etc) que você julgar necessário para ajudar a resolver o problema, assim como usar outras funções auxiliares desde que as mesmas sejam também descritas. Para tal, declare a estrutura de dados e comente seu funcionamento. O caso base é atingido quando o algoritmo encontrar o nó fim informado na busca. O projeto do algoritmo também deverá levar em conta que cada nó só pode ser visitado uma vez durante a busca, para evitar ciclagem, devendo ter algum mecanismo de ‘memória’ que permita ao algoritmo verificar se o nó já foi visitado alguma vez." É basicamente o Algoritmo de Dijkstra ao contrário, porém tem um problema, dijkstra pega o próximo menor caminho, no caso do exercício ele precisa do maior somatório dos dois nós(inicio e fim), e não do próximo maior caminho... um exemplo que ocorreu no meu programa é se começar do 3 e quiser ir pro 4 ele vai pegar o próximo maior caminho que seria 3-2-4(valor 12+1) o que seria errado sendo que o maior caminho entre os dois laços seria 3-1-4(valor 9+22). Nesse caso eu pensei que teria que fazer um programa que iria ver todos os caminhos e todas as somatórias na força bruta, o que eu não consigo/não sei, gostaria de alguma ajuda, o que eu já fiz está aí: #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #define inf int nos; int** add(){ //funcao adiciona recebe a matriz custo do usuario int origem, destino; do{ printf("Digite a quantidade de nós do grafo (min. 2): "); scanf("%d", &nos); }while(nos < 2); //printf("%d", nos); int **custo; //matriz custo de "nos" índices custo = (int **) malloc(nos*sizeof(int)); for (int i = 0; i < nos; i++){ custo[i] = (int *) malloc(nos* sizeof(int)); } for (int i = 0; i < nos; i++){ //zerando a matriz for (int j = 0; j < nos; j++){ custo[i][j] = 0; } } for (int i = 0; i < nos; i++){ //imprimindo so pra ver se deu certo for (int j = 0; j < nos; j++){ //não vai entrar no programa final printf("%2d ", custo[i][j]); } printf("\n"); } getchar(); getchar(); printf("Entre com as Arestas:\n"); //a partir daqui vai ler a origem, destino e peso do { do { printf("Origem da aresta (entre 1 e %d ou '0' para sair): ", nos); scanf("%d",&origem); }while (origem < 0 || origem > nos); if (origem) { do { printf("Destino da aresta (entre 1 e %d, menos %d): ", nos, origem); scanf("%d", &destino); }while (destino < 1 || destino > nos || destino == origem); do { printf("Custo (positivo) da aresta do vertice %d para o vertice %d: ", origem, destino); scanf("%d",&custo[origem-1][destino-1]); custo[destino-1][origem-1] = custo[origem-1][destino-1]; }while (custo[origem-1][destino-1] < 0); } }while (origem); return custo; } void imprime(int **custo){ for (int i = 0; i < nos; i++){ //ímprimindo matriz custo(não ENTRA NO PROG FINAL) for (int j = 0; j < nos; j++){ printf("%2d ", custo[i][j]); } printf("\n"); } getchar(); getchar(); } void procura(int **custo){ int vet[nos], inicio, fim; do{ printf("Digite o vertice de inicio e de fim desejados(entre 1 e %d): ", nos); scanf("%d %d", &inicio, &fim); }while(inicio < 1 || inicio > nos || fim < 1 || fim > nos || inicio == fim); for (int i = 0; i < nos; i++) vet[i] = 0; } int main (){ int op; int **custo; do{ system("clear"); printf("+----------NUMERO UM DO TP DE MD----------+\n" "0 - para sair\n1 - Inserir matriz custo\n2 - Inserir início e fim " "do grafo para calcular a maior distancia entre eles\n3 - Imprime matriz custo\nDigite a opcao: "); scanf("%d", &op); switch (op){ case 1: custo = add(); //aqui tá dando erro de segmentaçao break; case 2: procura(custo); break; case 3: imprime(custo); break; case 0: break; default: printf("Opcao invalida, pressione Enter para voltar ao menu... "); setbuf(stdin,NULL); getchar(); break; } }while (op != 0); return 0; } OBS1: O programa não está com o valor fixo do grafo então toda vez que for rodar precisa inserir todos os nós e valores. OBS2: O trabalho tem que ser em C. OBS3: Imagem do programa:

Preciso de um codigo em C do caminho minimo usando o algoritmo de Dijkstra, achei um na internet, ta funcionando direitinho, so q queria mudar ele pra poder escolher meu alvo e ele falar o caminho ate ele. Porque por ex, se eu coloco 4 vertices, ele pede certo o peso das arestas q eu ligar entres os 4 e da o caminho delas, mas não me pede meu alvo, porque posso querer saber o caminho da 2 para a 4, mas tambem posso querer da 1 para a 4. alguém PFVR SABE MUDAR? #include <stdio.h> #include <stdlib.h> #include <math.h> #define FLSH gets(l) int destino, origem, vertices = 0; int custo, *custos = NULL; void dijkstra(int vertices,int origem,int destino,int *custos) { int i,v, cont = 0; int *ant, *tmp; int *z; /* vertices para os quais se conhece o caminho minimo */ double min; double dist[vertices]; /* vetor com os custos dos caminhos */ /* aloca as linhas da matriz */ ant = calloc (vertices, sizeof(int *)); tmp = calloc (vertices, sizeof(int *)); if (ant == NULL) { printf ("** Erro: Memoria Insuficiente **"); exit(-1); } z = calloc (vertices, sizeof(int *)); if (z == NULL) { printf ("** Erro: Memoria Insuficiente **"); exit(-1); } for (i = 0; i < vertices; i++) { if (custos[(origem - 1) * vertices + i] !=- 1) { ant = origem - 1; dist = custos[(origem-1)*vertices+i]; } else { ant= -1; dist = HUGE_VAL; } z=0; } z[origem-1] = 1; dist[origem-1] = 0; /* Laco principal */ do { /* Encontrando o vertice que deve entrar em z */ min = HUGE_VAL; for (i=0;i<vertices;i++) if (!z) if (dist>=0 && dist<min) { min=dist;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) { if (custos[v*vertices+i] != -1 && dist[v] + custos[v*vertices+i] < dist) { dist = dist[v] + custos[v*vertices+i]; ant =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) { // printf("<-%d",i+1); tmp[cont] = i+1; cont++; i = ant; } for (i = cont; i > 0 ; i--) { printf("%d -> ", tmp[i-1]); } printf("%d", destino); printf("\n\tCusto: %d\n",(int) dist[destino-1]); } } void limpar(void) { printf("{FONTE}33[2J"); /* limpa a tela */ printf("{FONTE}33[1H"); /* poe o curso no topo */ } void cabecalho(void) { limpar(); printf("Implementacao do Algoritmo de Dijasktra\n"); printf("Comandos:\n"); printf("\t d - Adicionar um Grafo\n" "\t r - Procura Os Menores Caminhos no Grafo\n" "\t CTRL+c - Sair do programa\n"); printf(">>> "); } void add(void) { int i, j; do { printf("\nInforme o numero de vertices (no minimo 2 ): "); scanf("%d",&vertices); } while (vertices < 2 ); if (!custos) free(custos); custos = (int *) malloc(sizeof(int)*vertices*vertices); for (i = 0; i <= vertices * vertices; i++) custos = -1; printf("Entre com as Arestas:\n"); do { do { printf("Origem da aresta (entre 1 e %d ou '0' para sair): ", vertices); scanf("%d",&origem); } while (origem < 0 || origem > vertices); if (origem) { do { printf("Destino da aresta (entre 1 e %d, menos %d): ", vertices, origem); scanf("%d", &destino); } while (destino < 1 || destino > vertices || destino == origem); do { printf("Custo (positivo) da aresta 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 procurar(void) { int i, j; /* Azul */ printf("{FONTE}33[36;1m"); 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"); } printf("<Pressione ENTER para retornar ao menu principal>\n"); /* Volta cor nornal */ printf("{FONTE}33[m"); } int main(int argc, char **argv) { int i, j; char opcao[3], l[50]; do { cabecalho(); scanf("%s", &opcao); if ((strcmp(opcao, "d")) == 0) { add(); } FLSH; if ((strcmp(opcao, "r") == 0) && (vertices > 0) ) { procurar(); FLSH; } } while (opcao != "x"); printf("\nAte a proxima...\n\n"); return 0; } Creditos ao dono do codigo acima q n sei quem é.