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

Teoria dos Grafos: Problema de Caminho Máximo



Problema de Caminho de Custo Máximo (Longest Path Problem)

Em Teoria dos Grafos, define o conjunto de problemas que busca determinar qual o caminho mais custoso em um grafo.


Definição

  • Em um grafo, chama-se de custo de um caminho à soma dos pesos das arestas do caminho.
  • Um caminho é mais custoso do que outro se a soma dos pesos das suas arestas for maior. Se um determinado caminho não possuir outro caminho com mesma origem e término mais custoso do que ele, ele será o caminho de custo máximo.
  • Se não existe caminho entre um dado vértice de origem e outro vértice-final, o problema não possui solução.

Algoritmos de caminho máximo

Não existe ainda algoritmos eficientes para resolver o problema do caminho de custo máximo. Há porém alguns algoritmos em uso.

Algoritmo de força bruta

Este algoritmo examina todos os caminhos simples de um vértice-origem para um vértice-destino,  escolhendo aquele que tenha  custo máximo. 


Para citar este artigo

REVISTABW. Teoria dos Grafos: Problema de Caminho Máximo.Revista Brasileira de Web: Tecnologia. Disponível em https://www.revistabw.com.br/revistabw/problema-de-caminho-maximo/. Criado em: 29/12/2017. Última atualização: 29/12/2017. Visitado em: 22/07/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.