Каков самый простой алгоритм/решение для кратчайшего пути одной пары через вещественный неориентированный граф?

Мне нужно найти кратчайший путь через неориентированный граф, узлы которого являются вещественными (положительными и отрицательными) взвешенными. Эти веса подобны ресурсам, которые вы можете получить или потерять, введя node.

Общая стоимость (сумма ресурса) пути не очень важна, но она должна быть больше 0, а длина должна быть минимальной.

Например, рассмотрим такой граф:

A-start node; D-end node

A(+10)--B( 0 )--C(-5 )
     \     |    /
       \   |  /
D(-5 )--E(-5 )--F(+10)

Самый короткий путь будет A-E-F-E-D

Один только алгоритм Дийкстры не делает этого, потому что он не может обрабатывать отрицательные значения. Итак, я подумал о нескольких решениях:

Сначала используется алгоритм Дейкстры для вычисления длины кратчайшего пути от каждого node до выхода node, не учитывая веса. Это можно использовать как какое-то значение эвристики, как в *. Я не уверен, что это решение может работать, а также очень дорого. Я также подумал о реализации алгоритма Флойда-Варшалла, но я не уверен, как это сделать.

Еще одно решение заключалось в том, чтобы вычислить кратчайший путь с алгоритмом Дейкстры, не учитывая веса, и если после вычисления суммы ресурса пути оно меньше нуля, пройдите через каждый node, чтобы найти соседний node, который может быстро увеличить ресурса и добавьте его в путь (при необходимости несколько раз). Это решение не будет работать, если существует node, что может быть достаточно для увеличения суммы ресурса, но дальше от рассчитанного кратчайшего пути.

Например:

A- start node; E- end node
A(+10)--B(-5 )--C(+40)
      \
        D(-5 )--E(-5 )

Не могли бы вы помочь мне решить эту проблему?

EDIT: Если при расчете кратчайшего пути вы достигаете точки, где сумма ресурсов равна нулю, этот путь недействителен, поскольку вы не можете продолжать, если нет больше бензина.

Ответ 1

Это не похоже на элегантное решение, но, учитывая возможность создания циклических путей, я не вижу способа обойти это. Но я бы просто решил это итеративно. Используя второй пример - Начните с точки в точке A, дайте ей значение A. Переместите один "поворот" - теперь у меня есть две точки, одна на B со значением 5, а одна на D также со значением 5. Перемещение снова - теперь у меня есть 4 точки для отслеживания. C: 45, A: 15, A: 15 и E: 0. Возможно, что одно в E может осциллировать и стать действительным, поэтому мы не можем его отбросить. Перемещение и накопление и т.д. Когда вы достигнете конца node с положительным значением, которое вы сделали (хотя могут быть дополнительные эквивалентные пути, которые входят в один и тот же ход)

Очевидно, что проблема в том, что количество точек для трека будет расти довольно быстро, и я предполагаю, что ваш фактический график намного сложнее, чем пример.

Ответ 2

Изменить: я недостаточно хорошо читал вопрос; проблема более сложная, чем обычная проблема с одним источником кратчайшего пути. Я оставляю это сообщение только сейчас, чтобы дать вам еще один алгоритм, который может вам пригодиться.

алгоритм Беллмана-Форда решает проблему короткого пути с одним источником, даже при наличии краев с отрицательным весом. Однако он не обрабатывает отрицательные циклы (круговой путь на графике, весовая сумма которого отрицательна). Если ваш график содержит отрицательные циклы, вероятно, у вас проблемы, потому что я считаю, что это делает проблему NP-полной (поскольку она соответствует самой длинной простой проблеме пути).

Ответ 3

Я бы сделал это аналогично тому, что предложил Майкбе: сделайте первый поиск по графику возможных состояний, т.е. (положение, топливо-левый) -пары.

Использование вашего примера:

Octagons: вышло из топлива
Коробки: дочерние узлы опущены по соображениям пространства.

Поиск этого графа в ширину гарантированно даст вам самый короткий маршрут, который фактически достигнет цели, если такой маршрут существует. Если это не так, вам придется отказаться через некоторое время (после поиска узлов x или, может быть, когда вы достигнете node со счетом, большим, чем абсолютное значение всех отрицательных оценок, объединенных), так как граф может содержать бесконечные петли.

Вы должны быть уверены, что не должны немедленно прекратить поиск цели, если хотите найти самый дешевый путь (топливо мудрый), потому что вы можете найти несколько путей одинаковой длины, но с разными затратами.

Ответ 4

Попробуйте добавить абсолютное значение минимального веса (в данном случае 5) ко всем весам. Это позволит избежать отрицательных циклических путей.

Существующие алгоритмы кратчайшего пути требуют вычисления кратчайшего пути для каждого node, потому что на некоторых узлах он объединяет решения, которые помогут корректировать кратчайший путь в других узлах. Невозможно сделать это только для одного node.

Удачи.