Please enable / Bitte aktiviere JavaScript!
Veuillez activer / Por favor activa el Javascript![ ? ]

Teoria dos Grafos: Algoritmo de Dijkstra



Algoritmo de Dijkstra

Algoritmo para encontrar caminho mínimo entre os vértices de um grafo.

Concebido em 1956 pelo cientista da computação Edsger W.Dijkstra.

 


Pseudo-Código

 1  função Dijkstra(Grafo, origem):
 2
 3      cria conjunto de vértices Q
 4
 5      para cada vertice v em Grafo:
 6          distancia[v] ← INFINITO
 7          vertice_anterior[v] ← INDEFINIDO
 8          adicione v em Q
 9
10      distancia[origem] ← 0
11      
12      enquanto Q não vazio:
13          u ← vertice em Q com distancia [u] minima
15          remove u de Q 
16          
17          para cada vizinho v de u:
18              alt ← distancia[u] + tamanho(u, v)
19              if alt < distancia[v]:
20                  distancia[v] ← alt 
21                  vertice_anterior[v] ← u 
22
23      retorne distancia[], vertice_anterior[]

Para citar este artigo

REVISTABW. Teoria dos Grafos: Algoritmo de Dijkstra.Revista Brasileira de Web: Tecnologia. Disponível em https://www.revistabw.com.br/revistabw/algoritmo-de-dijkstra/. Criado em: 28/12/2017. Última atualização: 28/12/2017. Visitado em: 23/05/2018


Procurando mais conteúdos ? Utilize o campo de busca abaixo



Leia +



Você também deveria ler


O conteúdo da Revista Brasileira de Web é licenciado sob uma Licença Creative Commons Atribuição 3.0 Brasil, exceto quando especificado claramente em contrário. Este é um site de conteúdos diversos e dicas gerais e não substitui a consultoria de um profissional devidamente qualificado. Isto significa que os assuntos aqui abordados possuem caráter geral e podem não ser adequados no seu caso. Leia nossos Termos de Uso e Privacidade.