Нахождение кратчайшего пути, который проходит через произвольную последовательность узлов?

Question

В этот предыдущий вопрос ОП спросил, как найти кратчайший путь в графе, который идет от u к v, а также проходит через некоторый узел w.Принятым ответом, который был бы неплохим, было запустить алгоритм Дейкстры дважды - один раз для перехода от u к w и один раз для перехода от w к v. Это имеет временную сложность, равную двум вызовам алгоритма Дейкстры, то есть O (m +).n log n).

Теперь рассмотрим связанный вопрос - вам дана последовательность узлов u ₁ , u ₂ , ..., u _k и хотите найти кратчайший путь от u ₁ до u _k так, чтобы путь проходил через u ₁ , u ₂ , ..., u _k по порядку.Очевидно, что это можно сделать, запустив k-1 экземпляры алгоритма Дейкстры, по одному для каждой пары смежных вершин, а затем объединить кратчайшие пути вместе.Это занимает время O (км + kn log n).В качестве альтернативы, вы можете использовать алгоритм кратчайших путей всех пар, такой как алгоритм Джонсона, чтобы вычислить все кратчайшие пути, а затем объединить соответствующие кратчайшие пути вместе за O (mn + n ² log n) времени, что хорошо дляk намного больше, чем n.

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

Answer 1

Вместо того, чтобы запускать отдельные экземпляры алгоритма Дейкстры для поиска путей u(k) -> u(k+1) по одному пути за раз, может ли отдельный экземпляр модифицированного поиска Дейкстры быть запущенным на каждом узле в последовательности одновременно, причем пути формируются, когдарегионы поиска встречаются "в середине".

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

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

Простомысль.

РЕДАКТИРОВАТЬ: я думаю, я говорю о разнонаправленном варианте двунаправленного поиска , с таким количеством направлений, сколько есть узлов в последовательности {u(1), u(2), ..., u(m)}.

Answer 2

Я не понимаю, как мы можем сделать намного лучше, вот все, что я могу придумать. Предполагая, что граф не является ненаправленным, кратчайший путь от любого узла u к узлу v будет таким же, как путь от v к u (в обратном порядке, конечно).

Теперь, для вашего случая кратчайшего пути в порядке u1 u2 u3 .. un, мы можем запустить алгоритм Джикстры на u2 (и найти кратчайшие пути u1-u2, u2-u3 за один проход), затем на u4 (для u3-u4 и u4-u5), затем u6 .. и так далее. Это уменьшает количество раз, когда вы применяете Джикстра примерно вдвое. Обратите внимание, что по сложности это идентично исходному решению.

Answer 3

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

Answer 4

Рассматривая вашу проблему с точки зрения «разделяй и властвуй», для данного графа G есть n узлов, k из которых [1 <= k <= n] мы хотим пройти в порядке от 1-k (i1, i2, ..., ик), </p>

Скажем, f (j) - кратчайший путь от i1 до ij. Задача хорошо подразделяется (вы уже видите, куда это идет) на более мелкие случаи нахождения кратчайших путей, которые в конечном итоге превращаются в суммирование f (j) при переходе j от 1 к k. Следовательно, ваша задача минимально ограничена k-1 итерациями алгоритма Джикстры. Единственный способ улучшить его - это найти более быстрый алгоритм, чем у Джикстры, чтобы найти кратчайший путь между двумя точками.

По крайней мере, это мое мнение. / аспирант