Teoria dos Grafos: Problema de Caminho Máximo – Revista Brasileira da Web – Tecnologia @revistabw
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.
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.
Este algoritmo examina todos os caminhos simples de um vértice-origem para um vértice-destino, escolhendo aquele que tenha custo máximo.
Leia mais conteúdos sobre Teoria dos Grafos
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