Estrutura grafo com pesos

[for]

Boas pessoal

Precisava de uma ajudinha para tentar estruturar da melhor forma um grafo com pesos.

Tenho um grafo exemplo:

http://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/xfig/coelho-2011/aresta-biconexo-coelho.png

Em que do vértice 0 para o 2 por exemplo tenho 2 alternativas de caminho exemplo:

0 - 2 com os pesos de Km 10, tempo 10 , custo 2

0 - 2 com os pesos de 12, 12, 0.5.

Todas as arestas tem 2 ou mais alternativas de caminho, o meu objectivo é conseguir estruturar da melhor forma para depois conseguir chegar ao caminho mais curto escolhendo um dos pesos como critério.

Nos casos que estive a ver apenas tinha uma alternativa de caminho logo criava a matriz de adjacências sem problemas, mas algora como tenho varias alternativas de caminho tinha pensado em casa posição guardar uma lista para conseguir guardar a varias alternativas de caminho esta solução é possível? Existe alguma melhor?

Aguardo ajudas pessoal.

Cumps 😉

[HappyHippyHippo]

os caminhos são bidireccionais ou unidireccionais ?

[for]

São bidireccionais.

[HappyHippyHippo]

uma lista de nós e uma lista de ligações com referência para os nós, seria a implementação que faria

[for]

Sera que me consegues explicar melhor isso?

Normalmente o que eu fazia é adicionar o nos exemplo:

addVertex('A');

addVertex('B');

E depois adicionava a sua ligação e o peso, mas como estava a referir neste caso tenho varias alternativas.

[HappyHippyHippo]

nada te impossibilita de fazer algo como:

Vertice v1 = addVertice('A');
Vertice v2 = addVertice('B');
Conn c1 = addConnection(v1, v2, /* peso */ 10);

Edited February 8, 2016 at 01:20 AM by HappyHippyHippo

[for]

Isso é algo parecido com o que faço, mas como tenho o código neste momento, se voltasse a criar um caminho com v1 e v2 estava escrever por cima do que já estava criado.

[HappyHippyHippo]

Mas isso e um problema do teu codigo e nao do modelo que te disse

[for]

O meu código era para um exemplo simples, agora o que estou a tentar fazer é algo mais complexo. Não estava a perceber muito bem o teu modelo, mas voltei a ler e o que disseste foi o que referi no 1 tópico.

[for]

Outra questão para este grafo, qual será o melhor algoritmo para encontrar o melhor caminho? Dijkstra?