Реализация алгоритма Джонсона для всех пар кратчайших путей
Алгоритм Джонсона находит кратчайшие пути между всеми парами вершин во взвешенном ориентированном графе. Это позволяет некоторым весам ребер быть отрицательными числами, но не может существовать циклов с отрицательными весами. Он использует алгоритм Беллмана-Форда для повторного взвешивания исходного графика, удаляя все отрицательные веса. Алгоритм Дейкстры применяется к перевзвешенному графу для вычисления кратчайшего пути между всеми парами вершин.
Алгоритм Описание
Используя алгоритм Дейкстры, можно найти кратчайшие пути между всеми парами вершин в O(V 2 logV) . Однако Дейкстра не работает с отрицательными весами. Чтобы избежать этой проблемы, алгоритм Джонсона использует метод, называемый повторным взвешиванием.
Повторное взвешивание — это процесс, при котором вес каждого ребра изменяется для удовлетворения двух свойств:
- Для всех пар вершин u, v в графе, если кратчайший путь существует между этими вершинами до повторного взвешивания, он также должен быть кратчайшим путем между этими вершинами после повторного взвешивания.
- Для всех ребер (u, v) в графе они должны иметь неотрицательный вес (u, v) .
Алгоритм Джонсона использует метод Беллмана-Форда для повторного взвешивания ребер. Bellman-Ford также может обнаруживать отрицательные циклы веса, если они присутствуют на исходном графике.
Графическое представление
Список смежности немного изменен для представления графа. Для каждой исходной вершины s каждая из ее соседних вершин имеет два связанных с ними свойства:
- Назначения
- Масса
Рассмотрим график –
Исходная вершина 0 имеет одну соседнюю вершину, точка назначения которой равна 2 , а вес равен -2 . Каждая соседняя вершина инкапсулируется с помощью статического класса Neighbor .
Java
private static class Neighbour { int destination; int weight; Neighbour(int destination, int weight) { this.destination = destination; this.weight = weight; }} |
Псевдокод
Выполните следующие шаги, чтобы решить проблему:
- Добавьте в граф новую вершину q , соединенную ребрами нулевого веса со всеми остальными вершинами.
- Используйте алгоритм Беллмана-Форда, начиная с новой вершины q, чтобы найти для каждой вершины v минимальный вес h(v) пути из q в v. Если на этом шаге обнаруживается отрицательный цикл, алгоритм завершается.
- Перевзвешивание ребер исходного графа с использованием значений, вычисленных алгоритмом Беллмана-Форда: ребро от u до v, длина которого w(u, v) перевзвешивается до w(u, v) + h(u) − h(v ) .
- Удалите q и примените алгоритм Дейкстры, чтобы найти кратчайшие пути от каждого узла s до каждой другой вершины в перевзвешенном графе.
- Вычислите расстояние в исходном графе, добавив h(v) − h(u) к расстоянию, возвращаемому алгоритмом Дейкстры.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(V 2 log V + VE). Временная сложность алгоритма Джонсона становится такой же, как у Флойда Уоршалла , когда графы полные (для полного графа E = O(V 2 ). Но для разреженных графов алгоритм работает намного лучше, чем Floyd Warshall .
Вспомогательное пространство: O(V*V)