0
Нам задан направленный ациклический граф с произвольными весами на ребрах и двумя конкретными узлами, s и t, где степень s и внешняя степень t равна 0. Как определить кратчайший путь от s до t, который имеет положительную стоимость?Кратчайший положительный путь в направленном ациклическом графе
мое предположение https: // эн. wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm – helt
Bellman-Ford предоставит самый короткий путь st, но он может иметь отрицательную стоимость. Тогда что нам делать? Нам нужен кратчайший путь между s и t, который имеет положительную стоимость. –
либо модифицируют bf так, чтобы предотвратить движение по отрицательным краям, если они слишком сильно уменьшают текущую стоимость, либо выполняют цикл: поиск кратчайшего пути; если c (путь) <0 удаляет столько отрицательных ребер, которые содержатся в пути, а затем снова поиск. или удаление края по одному. (нет гарантии, если вы не получите все баллы за эту домашнюю работу) – helt