Введение
Компьютерный метод поиска пути, алгоритм планирования с тем же названием, – алгоритм Джонсона – это способ нахождения кратчайших путей между всеми парами вершин в взвешенном ориентированном графе. Он допускает наличие отрицательных весов рёбер, но не допускает циклов отрицательного веса. Алгоритм работает путём использования алгоритма Беллмана-Форда для вычисления преобразования входного графа, устраняющего все отрицательные веса, что позволяет применить алгоритм Дейкстры к преобразованному графу. Алгоритм назван в честь Дональда Б. Джонсона, впервые опубликовавшего эту технику в 1977 году. Аналогичная техника перевешивания также используется в алгоритме Суурбаля для поиска двух непересекающихся путей минимальной общей длины между одними и теми же двумя вершинами в графе с неотрицательными весами рёбер.
the scheduling algorithm of the same name
Johnson's algorithm is a way to find the shortest paths between all pairs of vertices in an edge weighted directed graph. It allows some of the edge weights to be negative numbers, but no negative weight cycles may exist. It works by using the Bellman–Ford algorithm to compute a transformation of the input graph that removes all negative weights, allowing Dijkstra's algorithm to be used on the transformed graph. It is named after Donald B. Johnson, who first published the technique in 1977. A similar reweighting technique is also used in Suurballe's algorithm for finding two disjoint paths of minimum total length between the same two vertices in a graph with non negative edge weights.
Пример
Первые три этапа алгоритма Джонсона изображены на иллюстрации ниже. Граф слева от иллюстрации содержит два ребра с отрицательным весом, но не содержит отрицательных циклов. На центральном графе показана новая вершина q, дерево кратчайших путей, вычисленное алгоритмом Беллмана-Форда с начальной вершиной q, и значения h(v), вычисленные для каждой другой вершины как длина кратчайшего пути от q до этой вершины. Обратите внимание, что все эти значения неположительны, поскольку от вершины q есть ребро нулевой длины к каждой вершине, и кратчайший путь не может быть длиннее этого ребра. Справа показан перевзвешенный граф, полученный заменой веса каждого ребра w(u,v) на w(u,v) + h(u) − h(v). В этом перевзвешенном графе все веса ребер неотрицательны, однако кратчайший путь между любыми двумя вершинами использует ту же последовательность ребер, что и кратчайший путь между этими же двумя вершинами в исходном графе. Алгоритм завершается применением алгоритма Дейкстры к каждой из четырех начальных вершин в перевзвешенном графе.
Анализ
Временная сложность этого алгоритма, использующего кучи Фибоначчи в реализации алгоритма Дейкстры, составляет: алгоритм использует время для стадии Беллмана — Форда и время для каждой из итераций алгоритма Дейкстры. Таким образом, когда граф разреженный, общее время может быть меньше, чем у алгоритма Флойда — Уоршалла, который решает ту же задачу за время .