Dúvida com exercício que envolve Dijkstra

Ssk_
(usa Ubuntu)

Enviado em 20/12/2016 - 00:27h

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."

http://i.imgur.com/MXt7FK7.png

É 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++){		//NAO 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(NAO 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 programa precisa ser em C.
OBS3: Imagem do programa:

https://scontent-grt2-1.xx.fbcdn.net/v/t34.0-0/p280x280/15577792_1213824995394900_376056078_n.png?oh...