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

Question

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

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

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

A-start node; D-end node

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

Кратчайшим путем будет AEFED

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

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

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

Например:

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

Could Youпомочь мне решить эту проблему?

РЕДАКТИРОВАТЬ: Если при вычислении кратчайшего пути вы достигнете точки, в которой сумма ресурсов равна нулю, этот путь недопустим, так как выне может продолжаться, если нет больше бензина.

Answer 1

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

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

Answer 2

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

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

Answer 3

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

Используя пример вашего графика:

• Восьмиугольники: закончилось топливо
• Ящики: дочерние узлы опущены из-за нехватки места

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

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

Answer 4

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

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

Удачи