Лекция 11. Кратчайшие пути (продолжение)

Point-to-point алгоритмы. Ранняя остановка алгоритма Дейкстры. Двунаправленный алгоритм Дейкстры. Алгоритм A*. Алгоритм Дейкстры с потенциалами. Выбор phi(v) = dist(s, v), -dist(v, t) и пути по нулевым дугам. Использование оценки s(v) = dist(v, t). Условие допустимости оценок - неравенство треугольника, оценка снизу. Пример: евклидово расстояние для плоского графа. Алгоритм A* как алгоритм Дейкстры на исходном графе с правилом выбора вершины d(v) + s(v) = min. Алгоритм ALT. Множество вершин-маяков. Путь из s в t: две оценки снизу расстояния до t. Объединение по всем маякам, запуск алгоритма A*. Оценка трудоёмкости O(L E log V). Метод Highway Hierarchy. Разбиение графа на области, рёбра между областями, граничные вершины. При поиске неконцевые области заменяются на полные графы, предподсчёт расстояний между граничными вершинами. Алгоритм Джонсона. Задача APSP, есть отрицательные веса. Потенциалы вершин и потенциальное преобразование графа. Изменение веса пути и цикла. Сохранение кратчайших путей. Допустимые потенциалы: приведённые веса неотрицательны. Если есть цикл отр. веса, то допустимых потенциалов нет. Использование d(s, v) в качестве допустимых потенциалов. Алгоритм: Форд-Беллман + алгоритм Дейкстры (|V| раз). Время работы O(V * Dijkstra).