Tabela entre a distancia de seis cidades

[mtm]

Boa tarde

Podem me ajudar nessa questão?


Na tabela abaixo estão indicadas distâncias entre seis cidades (se não aparece um
número, as cidades não estão conectadas, porém se aparece um número, pode-se ir em
ambas as direções, por exemplo podemos ir da A até B ou de B até A percorrendo
uma distância de 5 unidades):


B C D E F
A 5 4
B 9 6 2
C 8
D 3
E 3

Encontre o percurso mínimo entre A e D

[3,14159265]

Amigo,

Não seria melhor anexar essa tabela? Não deu pra entender nada.

[mtm]

Na tabela abaixo estão indicadas distâncias entre seis cidades (se não aparece um
número, as cidades não estão conectadas, porém se aparece um número, pode-se ir em
ambas as direções, por exemplo podemos ir da A até B ou de B até A percorrendo
uma distância de 5 unidades):


Encontre o percurso mínimo entre A e D

Grato desde já

Anexos

Na tabela abaixo estão indicadas distâncias entre seis cidades (se não aparece um
número, as cidades não estão conectadas, porém se aparece um número, pode-se ir em
ambas as direções, por exemplo podemos ir da A até B ou de B até A percorrendo
uma distância de 5 unidades): Encontre o percurso mínimo entre A e D

[Sobolev]

Se desenhar o grafo vai perceber imediatamente qual é a solução. O caminho mais curto entre A e D é o correspondente ao percurso A - B - F - E - D, com comprimento 13. Outros percursos seriam

A - B - D (comprimento 14)
A - B - E - D (comprimento 14)
A - C - E - D (comprimento 15)

[Baltuilhe]

Boa noite!

Para encontrar caminho mínimo conheço alguns algoritmos, mas acredito ser mais eficiente o algoritmo de Dijkstra.

Código:

INITIALIZE-SINGLE-SOURCE(G, s)
for each vertex v ∈ G.V
   v.d = ∞ // coloca em cada vértice o peso infinito
   v.π = NIL // atribui o 'pai' (pi) de cada vértice como NULO
s.d=0 // este é o vértice de início, atribui peso 0

RELAX(u, v, w) // calcula o peso dos vértices
if v.d > u.d+w(u,v) // se o peso do vértice 'v' (destino) for maior do que a soma do vértice 'u' (origem) com o peso da aresta (distância entre u e v)
   v.d =u.d+w(u,v) // atribui ao vértice destino a soma da origem com o peso da aresta
   v.π = u // atribui como 'pai' (vértice anterior) de 'v' o vértice 'u'

DIJKSTRA(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s) // inicializa todos os vértices
S=∅ // cria um conjunto S, vazio
Q=G.V // cria um conjunto com todos os vértices
while Q̸ <> ∅ // enquanto o conjunto dos vértices não estiver vazio (diferente de vazio)
   u = EXTRACT-MIN(Q) // retira um vértice do conjunto, o que tiver MENOR peso
   S = S ∪ {u} // insere este vértice no conjunto S
   for each vertex v ∈ G.Adj[u] // para cada vértice adjunto ao vértice retirado, ou seja, para cada vértice onde há um caminho para outro vértice
      RELAX(u, v, w) // aqui faz o 'relaxamento' dos vértices, conforme algoritmo


Usando o algoritmo anterior para todos os vértices, chegamos na seguinte conclusão:
A(0)
B(5) - pai A
C(4) - pai A
D(13) - pai E
E(10) - pai F
F(7) - pai B

Fica a sequência:
A(0)->B(5)->F(7)->E(10)->D(13)
A(0)->C(4)

Se quiser alguma ajuda a mais quanto à execução do algoritmo, só perguntar, ok?

Espero ter ajudado!