Алгоритм Джонсона на орграфе с отрицательными дугами

    Статья подготовлена в преддверии старта курса «Алгоритмы и структуры данных»





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


    О, как звучит! Давайте разберём условие задачи по частям.


    Граф, в котором каждое ребро имеет направление, называется ориентированным (или кратко – орграфом), а его рёбра называются дугами. Для примера, возьмём орграф из 4 вершин и 8 дуг:


    drawing


    Мы можем перемещаться из одной вершины в другую по дугам в указанном направлении. Перемещение по одной или нескольким дугам называется «путь» или «маршрут».


    Для каждой дуги может быть указано число, которое называется «вес» или «длина» дуги. Мы будем смотреть на каждое число, как на длину. Цель алгоритма – найти кратчайший путь между любыми двумя вершинами. В качестве разминки, найдите кратчайший путь из вершины А в вершину D и напишите ответ в комментариях, а мы продолжим.


    Вы, наверное, уже заметили, что некоторые дуги имеют отрицательный вес. Путешествие по таким дугам приносит доход. Мечтой путешественника было бы найти замкнутый путь с отрицательной длиной и ходить по нему вечно. Замкнутый путь называется «циклом» или «контуром», и если в орграфе есть такой негативный контур, то решение задачи отсутствует, так как минимальная длина пути может стремиться к минус бесконечности.


    Итак, мы разобрали все термины условия, сформулируем цель алгоритма ещё раз, более осознанно:


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


    Для решения этой задачи можно применить алгоритм Флойда-Уоршелла, который решает задачу «в лоб» полным перебором:


    for k = 1 to n // n – количество вершин в графе
        for x = 1 to n
            for y = 1 to n
                W[x][y] = min(W[x][y], W[x][k] + W[k][y])

    Значение W[x][y] элемента содержит длину кратчайшего пути из вершины х в вершину у.
    Начальные значения для W – это матрица смежности исходного графа. Вместо нулей нужно записать плюс бесконечность, так как путь между такими вершинами ещё не найден.


    Суть алгоритма в постоянном «релаксировании» длины маршрута. На каждой итерации мы пробуем попасть из X в Y через промежуточную вершину К, и если этот путь короче – запоминаем уменьшенную длину.


    Алгоритм Флойда-Уоршелла перебирает все возможные варианты построения путей, сложность у него просто бомбическая – кубическая, и если в графе вершин много – он будет работать слишком долго.


    Ещё есть эффективный алгоритм Дейкстры для поиска кратчайшего пути от одной вершины до всех остальных. Если применить алгоритм Дейкстры для каждой вершины, то мы получим кратчайшие пути для всех пар вершин, причём значительно быстрее, чем в алгоритме Флойда-Уоршелла.


    Однако, алгоритм Дейкстры некорректно работает с графом с отрицательными весами.


    drawing


    Например, при поиске от вершины А, на первом этапе будет найден кратчайший путь в вершину В (-2), а на втором этапе «кратчайшим» будет путь из В в D (-2+6=4). На этом алгоритм отрапартует о результате и закончит работу. Отрицательная дуга CD даже не будет рассмотрена и правильный ответ не будет найден.


    Вот так. Один алгоритм медленный, другой некорректный.


    Что же делать?


    Ответ очевиден: использовать алгоритм Джонсона! Идея гениальна: на основе данного орграфа сформировать новый орграф таким образом, чтобы в нём не было отрицательных дуг, а все кратчайшие пути были такими же. Пропустить полученный орграф через алгоритм Дейкстры и на выходе получить верный ответ!


    Как же нам сформировать такой орграф?


    Простое неверное решение – увеличить длину каждой дуги на константное значение, чтобы отрицательных значений не осталось. Почему этот вариант некорректный? Потому что он даёт фору более коротким маршрутам, безосновательно увеличивая суммарную длину на ту самую константу с каждой новой дугой.


    Например, если в предложенном графе длину каждой дуги увеличить на 4, то кратчайшим маршрутом из A в D станет прямой путь: 5 + 1 * 4 = 9. Тогда как правильный ответ из 3 дуг (A-B-C-D) получит лишних 12 грамм нагрузки и выпадет из конкуренции: -2 + 8 – 4 + 3 * 4 = 14.


    Итак, наша задача – изменить длину каждой дуги таким образом, чтобы избавиться от отрицательных дуг и чтобы все кратчайшие расстояния остались такими же. Как это организовать? Давайте к длине каждой дуги XY добавим h(X) и вычтем h(Y), где h(v) – «чистая» функция, которая определяет некоторое константное значение для каждой вершины.


    Получим такие длины дуг:



    Посмотрим, как в этом случае изменится длина каждого маршрута из вершины A в D:



    Как видим, любой путь из вершины A в D изменятся на одинаковую величину, h(A) – h(D), а, следовательно, все кратчайшие пути остаются такими же! Как раз то, что нужно.
    Осталось теперь найти подходящие значения функции h, чтобы модифицированные длины дуг стали неотрицательными.


    Рассмотрим, как можно рассчитать такие значения


    Для этого добавим в орграф новую вершину-исток S, из которой проведём нулевые дуги во все вершины графа. Обратим внимание, что добавление вершины S и дуг S* не изменяет кратчайших путей в исходном графе, потому как все добавленные дуги идут только из S, а «нулевого» маршрута в обратном направлении нет.


    drawing


    Теперь запустим алгоритм Беллмана-Форда, который найдёт кратчайшие пути от S до всех остальных вершин. Этот алгоритм N раз подряд перебирает все дуги на предмет «релаксации» кратчайших маршрутов из S во все остальные вершины. В таблице перечислены «значимые» итерации работы этого алгоритма, в каждом столбце указана очередная дуга, которая сокращает маршрут до одной из вершин:



    Результат работы этого алгоритма как раз и даст нам искомые значения функции h для каждой вершины. Суть этих значений – кратчайший путь из вершины S. Поскольку все дуги из S нулевые, то и значения функции h – неположительные. Но пусть это нас не смущает, главное, что полученные значения зафиксированы, не меняются, а, значит, мы можем пересчитать длины всех дуг исходного орграфа:


    drawing


    В итоге у нас получится орграф без отрицательных дуг:


    drawing


    Здесь нет отрицательных дуг, а все кратчайшие маршруты такие же, как и в исходном орграфе, здорово! Теперь мы можем со спокойной душой запустить алгоритм Дейкстры на этом орграфе для каждой вершины и получить правильные ответы.


    Посмотрим, как будут найдены кратчайшие маршруты из вершины А до всех остальных:



    В каждом столбце, рядом с новым значением кратчайшего маршрута, записана вершина, откуда мы в неё пришли. По этим буквам мы можем восстановить кратчайший путь. Например, кратчайший маршрут из A в D восстанавливается по последнему столбцу и записывается справа налево: A <= B <= C <= D, что и требовалось найти.


    итак, в этой статье мы рассмотрели идею алгоритма Джонсона на конкретном примере. Надеюсь, изучение этого алгоритма по Википедии теперь станет более понятным.




    Узнать подробнее о курсе «Алгоритмы и структуры данных»



    OTUS. Онлайн-образование
    Цифровые навыки от ведущих экспертов

    Комментарии 9

      +1
      Спасибо за статью — очень наглядно. А есть ли какие-то методы, позволяющие обсчитать граф с негативным циклом? Ну, к примеру, наложить условие, что по циклу можно проходить только 1 раз… или что-то в этом роде.
        0
        Алгоритм Беллмана-Форда позволяет определить наличие отрицательного контура — если при N-ом проходе были изменения, значит, есть цикл с отрицательной суммой. Да, вы можете запретить запретить проходить по одному ребру более одного раза.
          +1
          Спасибо. У меня была примерно такая же идея, но чтобы не писать свою реализацию — после нахождения контура я его заменял отдельной вершиной с весом равным одному проходу по контуру.

          Но не покидала мысль, что может быть ученые умы как-то более элегантно решают это задачу)
        +1
        На первой стадии алгоритма вместо обычного алгоритма Беллмана-Форда можно использовать его улучшенную версию под названием SPFA: Shortest Path Faster Algorithm.
        Хотя в худшем случае (на специально подобранном графе) у него вычислительная сложность такая же, как у обычного Форда-Беллмана, но зато на случайных графах работает во много раз быстрее.
        А пишется не сильно сложней: надо добавить очередь (как при поиске в ширину) и ещё булевский массив. В цикле берём очередную вершину из очереди и смотрим на смежные с ней. Если для какой-то из них оценку получается уменьшить, то кидаем вершину в очередь, но только если там её ещё нету (для быстрой проверки наличия в очереди как раз булевский массив и нужен).
          0
          Да, это логичная и хорошая оптимизация алгоритма — хранить список вершин, которые изменились и которые могут повлиять на очередные релаксации в графе. Спасибо за комментарий!
          +1
          Отличный разбор. Спасибо!
            0
            Суть алгоритма в постоянном «релаксировании» длины маршрута. На каждой итерации мы пробуем попасть из X в Y через промежуточную вершину К, и если этот путь короче – запоминаем уменьшенную длину.

            Несовсем верно. Суть алгоритма Флойда — это динамическое программирование, в котором на k-ой итерации ищутся все кратчайшие пути используя вершины 1...k в качестве промежуточных. Именно поэтому важен именно такой порядок циклов — средняя вершина должна идти внешним циклом.


            А главное, вы можете объяснить какой вообще смысл в этом алгоритме Джонсона? Почему бы просто не запустить алгоритм Форда-Беллмана из начальной вершины A и найти все нужные вам расстояния?

              0
              Спасибо за уточнение. Смысл алгоритма в повышении скорости поиска.
                0
                Смысл алгоритма в повышении скорости поиска.

                В смысле, повышения скорости поиска? Он же медленнее! Вместо одного форда беллмана этот алгоритм делает сначала вспомогательного форда беллмана (да еще и в расширенном на одну вершину графе), а потом еще и дейкстру.

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое