Dúvida com exercício que envolve Dijkstra

[Ssk_]

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: