Найти кратчайший путь, который проходит через некоторую произвольную последовательность узлов?
в Это более ранний вопрос ОП задал, как найти кратчайший путь в графе, который идет от U в V, а также проходит через некоторое узел w. Принятый ответ, который довольно хорош, должен был пробежать алгоритм Dijkstra дважды - один раз, чтобы добраться от U до W и один раз, чтобы получить от W - v. Это имеет временную сложность, равную двум призывам в алгоритм Dijkstra, который является O (M + n log n).
Теперь рассмотрим связанный вопрос - вам дают последовательность узлов U 1 , U 2 , ..., u k и хочу найти Самый короткий путь от U 1 к U k k К К К К К К К К К К К K К К , что путь проходит через U 1 , U 2 , ..., u k в порядке. Очевидно, что это может быть сделано с помощью экземпляров K-1 алгоритма Dijkstra, по одному для каждой пары соседних вершин, затем объединяющих кратчайшие пути вместе. Это требует времени o (км + k n log n). В качестве альтернативы, вы можете использовать все пары кратчайших путей алгоритма, подобно алгоритму Джонсона, чтобы вычислить все кратчайшие пути, а затем объединить соответствующие кратчайшие пути вместе в O (Mn + N 2 . Log n) Время, которое хорошо для k намного больше, чем n.
Мой вопрос заключается в том, есть ли алгоритм для решения этой проблемы, который быстрее, чем приведенные выше подходы, когда k мало. Существует ли такой алгоритм? Или итерация, как это хорошо, так как он получает?