Definitivo
Na fila
Arestas verificadas

  • Atual
  • Na fila
  • Definitivo
  • Caminho
Um clique num nó define

Mais sobre o algoritmo de Dijkstra

Algoritmo de Dijkstra

O algoritmo de Dijkstra encontra o caminho mais curto de uma origem até cada um dos outros nós quando as arestas têm comprimentos, como as estradas entre cidades. Cresce para fora a partir da origem, retirando sempre o nó mais próximo que ainda não terminou. Clique num nó para começar a partir dele, escolha um destino se quiser e avance passo a passo para ver a fila, cada distância a descer quando surge um caminho mais curto, e o caminho mais curto a aparecer. Prima Reproduzir para ver a pesquisa, ou Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto. Clique num nó para o tornar a origem; mude o clique para Destino e clique noutro nó para procurar um caminho mais curto até ele. O número em cada aresta é o seu comprimento, o número em cada nó a sua distância mais curta até agora, e a linha por baixo do grafo é a fila, com o mais próximo primeiro. Novo grafo cria outro grafo; escolha quantos nós e arestas tem. Com o tabuleiro selecionado, as setas avançam e recuam um passo, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.

Como funciona

  1. Clique num nó para o tornar a origem. Para procurar um caminho, mude o clique para Destino e clique noutro nó.
  2. Prima Reproduzir, ou use Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto da pesquisa.
  3. Observe a fila por baixo do grafo e a distância em cada nó. Novo grafo cria outro grafo para experimentar.

Como funciona o algoritmo de Dijkstra

Dê à origem a distância 0 e a todos os outros nós infinito, e coloque a origem numa fila. Depois repita: retire o nó da fila com a menor distância e marque essa distância como definitiva. Para cada vizinho que não seja definitivo, some o comprimento da aresta à distância do nó. Se a soma for menor do que a distância que o vizinho tinha, passa a ser a sua nova distância, o nó fica registado como o caminho até lá, e o vizinho entra na fila se ainda não estava. Quando a fila fica vazia, cada nó alcançável tem a sua distância mais curta.

Porque é que o nó mais próximo é definitivo

Quando um nó é o mais próximo na fila, qualquer outro caminho até ele tem de sair da parte terminada do grafo por algum nó da fila, que está pelo menos tão longe, e depois somar arestas que não podem ser negativas. Por isso, nenhum outro caminho pode ser mais curto. É também por isso que um destino só é certo quando sai da fila, e não quando é alcançado pela primeira vez, e que o algoritmo de Dijkstra falha com arestas negativas: aí é preciso o algoritmo de Bellman–Ford. Quando todas as arestas têm comprimento 1, o algoritmo de Dijkstra faz o mesmo que a pesquisa em largura.

Perguntas frequentes

O que é o algoritmo de Dijkstra?

Uma forma de encontrar os caminhos mais curtos de um nó de origem até todos os outros nós de um grafo cujas arestas têm comprimentos iguais ou superiores a zero. Retira repetidamente o nó por terminar mais próximo, torna a sua distância definitiva e usa as suas arestas para encurtar as distâncias dos vizinhos.

Porque é que o algoritmo de Dijkstra não funciona com arestas negativas?

Torna a distância de um nó definitiva assim que esse nó é o mais próximo na fila. Uma aresta negativa encontrada mais tarde ainda poderia levar de volta a esse nó por um caminho mais curto, e a distância definitiva estaria errada. O algoritmo de Bellman–Ford lida com arestas negativas, desde que não haja um ciclo com total negativo.

Qual é a diferença entre Dijkstra e BFS?

A pesquisa em largura conta arestas e usa uma fila simples. O algoritmo de Dijkstra soma comprimentos de arestas e usa uma fila de prioridade que dá sempre o nó mais próximo. Com todas as arestas de comprimento 1, ambos encontram as mesmas distâncias.

Quão rápido é o algoritmo de Dijkstra?

Com um heap binário como fila de prioridade, o trabalho cresce com (V + E) log V para V nós e E arestas. Com um heap de Fibonacci, é E + V log V. A aplicação guarda a fila como uma lista ordenada, simples de mostrar e suficiente para grafos pequenos.

O meu grafo é enviado para algum lado?

Não. O grafo é criado e percorrido no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Ir para o editor