Алгоритм Джонсона

Алгоритм Джонсона

Алгоритм Джонсона вычисляет кратчайшие пути для любой пары вершин в график. У него хороший сложность для разреженных графов (несколько ребер по сравнению с количеством вершин).

Он использует алгоритмы Дейкстра и из Беллман Форди возвращает либо матрицу весов кратчайших путей, либо утверждение, что граф имеет путь с отрицательным весом.
Используемый метод состоит в том, чтобы вернуться к случаю только с положительными весами, а затем запустить алгоритм Дейкстры, начиная с каждой вершины. Если веса не все положительны, мы переопределяем их, чтобы можно было свести к первому случаю.

Алгоритм Джонсона состоит из следующих шагов:

  1. Добавить новый узел д к графу, и соединить этот узел дугами нулевого веса со всеми остальными узлами.
  2. Используйте алгоритм Беллмана-Форда, начиная с нового узла д определить для каждой вершины в, минимальный вес час(в) с пути д в в. Если обнаружен отрицательный цикл, алгоритм останавливается на сбое.
  3. Отвечать дуги исходного графика с использованием значений, рассчитанных по алгоритму Беллмана-Форда: дуга а в в, прежний вес или длина которого есть число ш(и,в), имеет для новой длины неотрицательное число ш(и,в) + ч (у)Н в).
  4. удалить верх д и использовать алгоритм Дейкстры для определения кратчайших путей.

Пример алгоритма Джонсона:

Алгоритм Джонсона с одним источником кратчайшего пути
Делиться
ru_RURU
%d такие блоггеры, как: