Максимальная прибыль с использованием алгоритма Дейкстры

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

ln=∞ for all n∈N∖{s}, ls=0
 N′={s}, N′′=∅
 repeat
     n=argminn′∈N′ln′ N′=N′∖{n}, N′′=N′′∪{n}
     for all (n,m)∈A with m∈N∖N′′ do
         if lm>ln+cn,m then
               lm=ln+cn,m N′=N′∪{m}
         end if 
     end for until (N′=∅ or t∈N′′)

max algorithm shortest-path dijkstra
person user2947416    schedule 23.04.2014    source источник
comment
Каков желаемый результат при наличии положительного цикла? Вы хотите самый длинный путь, который не включает в себя цикл (это сложно), или вы просто хотите получить ответ, как будто есть положительный цикл, вы можете получить столько прибыли, сколько захотите.   -  person Niklas B.    schedule 24.04.2014

Ответы (2)


arrow_upward
3
arrow_downward

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

«Самый длинный путь между двумя заданными вершинами s и t во взвешенном графе G — это то же самое, что и кратчайший путь в графе −G, полученный из G путем замены каждого веса на его отрицание. Следовательно, если кратчайшие пути могут быть найдены в −G, то самые длинные пути также можно найти в G. Для большинства графов это преобразование бесполезно, поскольку оно создает циклы отрицательной длины в −G. Но если G — ориентированный ациклический граф , то нельзя создавать отрицательные циклы, а самые длинные пути в G можно найти за линейное время, применяя алгоритм линейного времени для поиска кратчайших путей в −G, который также является ориентированным ациклическим графом.", как показано на вики-статья.

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

person cnsumner    schedule 23.04.2014
comment
Невзвешенные графы можно рассматривать как частный случай взвешенного графа, в котором все веса ребер равны 1. Итак, если вы можете эффективно решить проблему для взвешенных графов (как вы утверждаете), то вы можете сделать это и для невзвешенных графов. - person mastov; 17.10.2016

arrow_upward
3
arrow_downward

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

Беллмана-Форда также можно изменить, чтобы проверить, есть ли положительный цикл: в конце просто выполните еще одну итерацию. Если узел расслабляется, он достижим из положительного цикла, и вы можете выполнить обратный поиск в глубину в самом длинном дереве путей, чтобы найти цикл.

Конечно, если вы хотите найти самый длинный простой путь (без повторений ребер/узлов), проблема будет NP-сложной, как указал Rocks25.

person Niklas B.    schedule 24.04.2014