Teoria dos Grafos: Problema do caminho mínimo




Problema do caminho mínimo (Shortest path problem)

Em Teoria dos Grafos, é o nome dado ao problema de encontrar uma ligação entre dois vértices (ou nós) de interesse de um grafo, cujo custo seja minimizado (i.e., o menor possível).


Tipos de problemas de caminho mínimo

O problema de caminho mínimo pode possuir as seguintes variações:

  • Problema do caminho mínimo de origem única: deve-se encontrar os caminhos mais curtos a partir de um vértice desejado para todos os outros vértices no grafo.
  • Problema do caminho mínimo com destino único: no qual deve-se encontrar os caminhos mais curtos entre todos os vértices de um grafo em relação a um único vértice-destino.
  • Problema de caminho mais curto de todos os pares: deve-se encontrar os caminhos mais curtos entre cada par de vértices do grafo.

 


Algoritmos de caminho mínimo

Não existe um algoritmo que resolva o problema de menor caminho de forma absoluta. Há porém, na literatura, propostas de algoritmos apropriados para diferentes tipos de abordagem:

  • Algoritmo de Dijkstra
  • Algoritmo de Bellmann-Ford
  • Algoritmo de Floyd-Marshall
  • Algoritmo A-Star
  • Algoritmo de Johnson

Para citar este artigo

REVISTABW. Teoria dos Grafos: Problema do caminho mínimo.Revista Brasileira de Web: Tecnologia. Disponível em https://www.revistabw.com.br/revistabw/problema-do-caminho-minimo/. Criado em: 28/12/2017. Última atualização: 28/12/2017. Visitado em: 21/08/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.