Кратчайший путь от одного источника, который проходит через N ребер ?
В своих экономических исследованиях я в настоящее время имею дело с конкретной проблемой кратчайшего пути:
Учитывая направленный детерминированный динамический граф с весами на ребрах, мне нужно найти кратчайший путь от одного источника S, который проходит через N ребер. Граф может иметь циклы, веса ребер могут быть отрицательными, и путь может проходить через вершину или ребро более одного раза.
Существует ли эффективный алгоритм решения этой проблемы?
Что я уже пробовал:
Пока я могу вычислить кратчайший путь только тогда, когда знаю конечную вершину как ограничение, но теперь я хочу, чтобы мое ограничение было на количестве ребер, через которые проходят пути, а не на конечной вершине.
Gerry Schmitz
Итак, вы говорите, что я могу "повернуть вспять", чтобы "сократить" свой путь, выбрав отрицательное ребро, которое возвращается к предыдущей вершине, имеющей любое количество ребер?
Значит, существует потенциал для циклического превращения в отрицательную черную дыру?