Найти кратчайший путь от источника к цели во взвешенном неориентированном графе за время O (V + E)

Question

Мне было поручено разработать алгоритм, который находит кратчайший путь во взвешенном неориентированном графе с V узлами и E ребрами за O (V + E) времени. Веса всех графов являются положительными целыми числами, и ни один из них не превышает 15.

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

Зная во время выполнения BFS и DFS, я думаю, что какая-то модификация с этими алгоритмами приведет меня к O (V + E), но я не уверен, в каком направлении двигаться иликак я могу использовать ограничение веса <= 15 по краям. </p>

Любая помощь приветствуется.

Answer 1

Вы можете использовать алгоритм Дейкстры, но вы должны быть немного осторожны с очередью приоритетов.

Поскольку все веса являются целыми числами от 1 до 15, в очереди может быть только 16 различных приоритетов вв любое время. Вы можете использовать этот факт для реализации всех ваших приоритетных операций очереди в постоянное время. Это изменит сложность алгоритма с O (| V | + | E | log | V |) на O (| V | + | E |)

Есть много способов сделать эту очередь приоритетов,По сути, вы разделяете записи на списки записей с одинаковым приоритетом, и тогда вам нужно только расставить приоритеты для 16 списков. Разумно хранить эти 16 списков в круговом массиве.

Answer 2

Алгоритм, который Вы ищете, называется Алгоритмом набора, так как он работает также в графиках, которые содержат циклы. Это сложность O(E + WV). В случае, W>>V вы можете заменить одну корзину на W корзинами для весов 1, 2-3, 4-7, 8-15 etc.

Это оптимизация на Дейкстре, которая использует тот факт, что с учетом диапазона весов вывозможность заменить кучу Фибоначчи на сегменты, которые уменьшат операцию find_node с O(logn) до O(1).

Подробно алгоритм описан в GeeksForGeeks и Wikipedia среди других.

Вас также может заинтересовать Направленный ациклический граф Кратчайший путь в книге Кормена «Введение в алгоритмы» на с. 655 или GeeksForGeeks