Grafos ponderados e caminho mínimo – algoritmo de Dijkstra

O que mostra

Uma rede de estradas pode ser modelada como um grafo ponderado: os vértices são lugares, as arestas são estradas e cada peso é uma distância em quilômetros. O algoritmo de Dijkstra encontra caminhos mínimos a partir de um vértice de partida mantendo um rótulo provisório de distância em cada vértice: a cada passo fixa o vértice não fixado de menor rótulo e atualiza os rótulos dos seus vizinhos. Como todos os pesos são positivos, um rótulo fixado não pode mais melhorar. A simulação mostra também os graus dos vértices, cuja soma é o dobro do número de arestas e que, num grafo conexo, decidem se existem caminhos e circuitos eulerianos.

Como usar

Escolha um Mapa e selecione a partida e o destino em De e Para. Pressione Próximo passo várias vezes e peça aos alunos que prevejam qual vértice será fixado e quais rótulos vão mudar; use Passo anterior para rever uma decisão. Compare a rota final com a rota que usa menos estradas. Depois, em Clicar numa aresta, escolha fechar / abrir estrada, feche uma estrada do caminho mínimo e pressione Executar tudo para ver a nova rota.

Parâmetros que você pode mudar

• Mapa Cidade (7 lugares), Distritos da região (9 lugares)
• Vértice de partida
• Vértice de chegada

Perguntas para explorar

1. Por que o rótulo de um vértice nunca muda depois de ser fixado?
2. A rota com menos arestas é sempre a mais curta? Que exemplo do mapa mostra isso?
3. Quais estradas você poderia fechar para que as estradas restantes continuem conectadas e o grafo tenha um circuito euleriano?