Problema de caminho de capacidade máxima com restrições

Question

Eu estava tentando desenvolver um algoritmo para o máximo problema de capacidade com restrições, mas não consegui descobrir as alterações necessárias para a saída correta. O problema é:
Dado um gráfico não direcionado com dois parâmetros (peso, custo).Precisamos encontrar o Problema de caminho máximo de capacidade da origem para o destino, tal que o custo do caminho (soma das bordas do caminho) está dentro de um valor fixo especificado pelo usuário.Em outras palavras, (soma do parâmetro de custo ao longo do caminho) é limitada superior por um valor constante.
Eu modifiquei o algoritmo existente adicionando e restrição de custos extra enquanto relaxava as bordas, mas não conseguiu fazer funcionar para todos os tipos de gráfico.Eu também estava me perguntando se esse problema é NP-completo.

Answer 1

Pode ser resolvido em tempo polinomial.Por exemplo, você pode usar a pesquisa binária sobre o peso.Dado um peso candidato, exclua todas as bordas com menor peso, então encontre o caminho mais baixo de custo e teste se seu custo está abaixo do limite inferior;Isso diz a você se o peso era muito alto ou muito baixo.Repita até que a pesquisa binária seja convergente.