Можем ли мы изменить алгоритм Дейкстры для работы с отрицательными весами?
Псевдокод, взятый из Википедии:
function Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 dist[v] := infinity ; // Unknown distance function from source to v
4 previous[v] := undefined ; // Previous node in optimal path from source
5 end for ;
6 dist[source] := 0 ; // Distance from source to source
7 Q := the set of all nodes in Graph ; // All nodes in the graph are unoptimized - thus are in Q
8 while Q is not empty: // The main loop
9 u := vertex in Q with smallest distance in dist[] ; // Start node in first case
10 if dist[u] = infinity:
11 break ; // all remaining vertices are inaccessible from source
12 end if ;
13 remove u from Q ;
14 for each neighbor v of u: // where v has not yet been removed from Q.
15 alt := dist[u] + dist_between(u, v) ;
16 if alt < dist[v]: // Relax (u,v,a)
17 dist[v] := alt ;
18 previous[v] := u ;
19 decrease-key v in Q; // Reorder v in the Queue
20 end if ;
21 end for ;
22 end while ;
23 return dist[] ;
24 end Dijkstra.
Теперь в строке 14 мы видим, что релаксация применяется только к соседям u которые еще не были удалены из Q, Но если мы возьмем также соседей u которые были удалены из Q Мне кажется, что алгоритм работает с отрицательными весами. Я не нашел ни одного случая, который противоречит этому утверждению.
Так почему алгоритм Дейкстры не изменяется таким образом?
6 ответов
Дейкстра может позволить себе посещать каждый узел один и один раз, потому что когда он выбирает новый узел для посещения, он выбирает непосещенный узел, который имеет кратчайший путь от корня. Как следствие, он может с уверенностью предположить, что нет более короткого пути к этому узлу через другой не посещаемый узел (потому что, если лучший из известных вам способов от A до B стоит 2, а лучший путь от A до C стоит 3, нет никакого шанса найти лучший путь от A до B, такой как A>C>B).
Если вы добавите отрицательные веса, вы внезапно нарушите это предположение.
Конечно, вы можете использовать предложенную вами модификацию, но тогда вы потеряете преимущество посещения каждого узла только один раз; и, таким образом, он потеряет прирост производительности по сравнению с другими алгоритмами, такими как Ford-Bellman
Конечно, вы можете заставить алгоритм Дейкстры работать с отрицательными значениями, просто убедившись, что вы не пересекаете ни один узел или ребро дважды. Здесь под работой я имею ввиду прекращение. Результат, однако, не может быть оптимальным.
Алгоритм Дейкстры имеет жадный смысл. Представьте себе следующий график:
A --- 1 --- B
| |
3 -4
| |
C -- -1 --- D
Если мы хотим перейти от A к B, лучшим путем будет ACDB, но алгоритм Дейкстры находит AB. Вы не можете заставить алгоритм Дейкстры предсказывать будущее, потому что это жадный алгоритм. Предсказывая будущее, я имею в виду, зная, что в дальнейшем стоимость пути может быть уменьшена. Обратите внимание, что это означает, что ваша модификация будет работать неправильно, если она будет применена к версии алгоритма Дейкстры, которая завершается, как только виден пункт назначения. В опубликованной вами версии ваша модификация работает, за исключением того, что есть более эффективные способы обработки отрицательных граней (см. Комментарии).
Как примечание, кратчайший путь в неориентированных графах с отрицательными значениями или ориентированных графах с отрицательными циклами даже не имеет смысла!
У вас есть в основном два варианта.
Вы можете изменить алгоритм, как вы предлагаете. Если у вас есть направленный граф без отрицательного цикла, то это правильный алгоритм, но он может быть очень медленным (потому что вы будете посещать каждый узел много раз). Я думаю, что есть случай, когда этот алгоритм имеет экспоненциальную временную сложность.
Вы можете изменить стоимость ребер с помощью потенциалов. Каждая вершина имеет некоторый потенциал h (v), и вес для ребра u->v будет равен w(u,v) + h(u) - h(v). Обратите внимание, что это не влияет на то, какой путь между данными двумя вершинами (s, t) является самым коротким, только его стоимость изменяется h(s) - h(t). Но вам нужно рассчитать потенциал. Хороший способ сделать это предлагается здесь: http://en.wikipedia.org/wiki/Johnson%27s_algorithm
Нет, не возможно, как указано. Алгоритм не имеет смысла с отрицательными весами, если вы строго не ограничите предоставленный тип графика.
Предположим, что граф с узлами A, B, C и ребрами с весами AB=-1, BA=0, BC=1.
Теперь уже не существует кратчайшего пути между А и С, и вы всегда можете сделать более короткий путь, переместившись назад и вперед между А и В еще раз.
Конечно, алгоритм все еще будет работать, но он даст неправильные ответы.
Да, ваша модификация будет работать при 2 допущениях, которые вы не упомянули, но я предполагаю, что это подразумевается:
- Кратчайшие пути должны быть фактически определены в вашем входном графе. Если вы отмените ограничение на неотрицательные веса, вы должны по крайней мере потребовать, чтобы не было циклов с отрицательным весом.
- Операция "клавиша уменьшения v в Q" в строке 19 не имеет смысла для узлов v, которые не находятся в Q. Но, конечно, вы можете повторно добавить их в Q с новым значением.
Однако вы потеряете важную особенность алгоритма Дейкстры: его хорошую асимптотическую производительность в худшем случае. Готовый Dijkstra гарантирует хорошую производительность, потому что он посещает каждый узел и каждое ребро не более одного раза. С учетом внесенных изменений узлы, которые уже были удалены, могут повторно добавляться в очередь приоритетов, и, возможно, большие части графика должны посещаться снова и снова. В худшем случае вам нужно выполнить столько же ослаблений, сколько, например, алгоритму Беллмана-Форда, но у вас есть дополнительные издержки очереди с приоритетами. Это ухудшает производительность в худшем случае по сравнению с Bellman-Ford, что предпочтительнее для графиков с отрицательными краями.
Это не значит, что ваш модифицированный Dijkstra бесполезен. Он может работать намного лучше, чем Bellman-Ford, если у вас очень мало отрицательных ребер и / или если эти отрицательные ребра отделены от остальной части графика дорогими путями. Но будьте готовы к довольно плохой производительности в худшем случае.
Ну, просто расслабить уже посещенные узлы в модифицированной версии Dijkstra недостаточно (и это даст вам неправильный ответ в графе, содержащем отрицательные ребра). Более того, вам нужно поместить ЛЮБОЙ расслабленный край в ваш контейнер (например, приоритетную очередь или просто очередь). Следовательно, вы можете изменить код из строки 19 следующим образом:
if v is in priority queue
then decrease-key(v)
else
add v into priority queue
В этом случае ваш алгоритм может работать. Кроме того, эффективность для модифицированной версии Дейкстры не будет уменьшаться для положительного взвешенного графика. Это может быть легко доказано, потому что это естественно жадный алгоритм.
Однако для графов, содержащих отрицательные ребра, новый алгоритм может стать медленным с точки зрения теоретического анализа, но он будет хорошо работать на практике.
На самом деле, вы можете взглянуть на алгоритм под названием SPFA(Алгоритм кратчайшего пути), опубликованный Dingfan Duan в Китае (1994). Многие OIer(Olympic of Info) знают, что этот алгоритм иногда может побить Дейкстру.