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

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

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

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

Ответ 1

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

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

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

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

EDIT: Я думаю, что я говорю о многонаправленном варианте двунаправленного поиска, с таким количеством направлений, как есть узлов в последовательности {u(1), u(2), ..., u(m)}.

Ответ 2

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

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

Ответ 3

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

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

По крайней мере, я беру на себя это. /grad student

Ответ 4

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