Здравствуйте, FlameHeap, Вы писали:

А замена весов на отрицательные и поиск наименьшего решения приводит к полному перебору графа, что опять таки неприемлемо...

Что значит к "полному перебору" ?!