кратчайший путь между 2 вершинами в неориентированном взвешенном графе

Question

Я пытаюсь найти кратчайший путь между 2 вершинами в неориентированном взвешенном графе.Также известно, что веса являются целыми числами меньше, чем log (log | V |), где | V |это количество вершин.Это легко решить, используя алгоритмы Беллмана-Форда или Дейкстры, но есть ли какой-нибудь алгоритм, который может сделать это быстрее?

До сих пор я думал об использовании BFS и делении ребер с весом больше 1 на паруиз них с весом 1, но это не очень хорошая идея, если | V |это большое количество.Нет, это не моя домашняя работа, мне просто интересно.

Answer 1

Одним из способов решения этого вопроса является улучшение времени использования алгоритма Дейкстры для нахождения кратчайшего пути между двумя вершинами в неориентированном взвешенном графе.Таким образом, в этом случае вы можете использовать двоичную кучу в качестве структуры данных.Куча - это полное двоичное дерево со свойством кучи, что каждый родительский узел меньше (больше), чем его дочерние узлы в дереве в минимальной куче (максимальная куча).Здесь вы можете использовать минимальную кучу для хранения стоимости каждого узла от начального узла.

Более подробную информацию о куче можно найти здесь: https://courses.csail.mit.edu/6.006/fall10/handouts/recitation10-8.pdf

С кучей время работы алгоритма Дейкстры может быть уменьшено с O (V ^ 2) до O (E log E), поскольку для выбора минимального расстояния из кучи требуется O (log V) (для удаления минимального расстояния - O (1), а для исправления кучи - O (log V)), а для обновления расстояний до вершин требуется O (E log V) ввсего (исправление кучи занимает O (log V) и E раз для проверки соседей и изменения затрат).

Надеюсь, эта помощь.