Алгоритм Джонсона: все кратчайшие пути в разреженном графе

Коротко

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

Зачем он нужен

Флойд-Уоршелл всегда работает за O(V³) независимо от числа рёбер. При 1000 вершин это миллиард операций, даже если рёбер всего 2000.

Дейкстра из каждой вершины дала бы O(V·E·log V), что для разреженного графа гораздо лучше. Но Дейкстра не работает с отрицательными весами.

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

Хитрость перевешивания

Назначим каждой вершине потенциал h[v]. Новый вес ребра:

w'(u, v) = w(u, v) + h[u] − h[v]

Почему кратчайшие пути сохраняются. Возьмём путь из s в t через промежуточные вершины. Сумма новых весов:

(w₁ + h[s] − h[a]) + (w₂ + h[a] − h[b]) + ... + (wₖ + h[y] − h[t])

Все промежуточные потенциалы сокращаются телескопически, остаётся:

исходная длина пути + h[s] − h[t]

То есть все пути из s в t изменились на одну и ту же величину. Значит порядок между ними сохранился, и кратчайший остался кратчайшим.

Откуда взять потенциалы

Нужно, чтобы w(u,v) + h[u] − h[v] ≥ 0, то есть h[v] ≤ h[u] + w(u,v). Это в точности условие корректности кратчайших расстояний.

Значит потенциалы можно получить, посчитав кратчайшие расстояния от какой-то вершины. Чтобы достать все вершины, добавляем фиктивный источник, соединённый со всеми рёбрами нулевого веса, и запускаем Беллмана-Форда (он умеет отрицательные веса).

Побочный бонус: Беллман-Форд заодно обнаружит отрицательный цикл, при котором задача не имеет решения.

Реализация

import heapq


def johnson(graph: dict):
    """graph: {вершина: [(сосед, вес)]}. Возвращает {u: {v: расстояние}}."""
    vertices = list(graph)

    # 1. фиктивный источник, соединённый со всеми нулевыми рёбрами
    SRC = object()
    extended = {v: list(graph[v]) for v in graph}
    extended[SRC] = [(v, 0) for v in vertices]

    # 2. Беллман-Форд для потенциалов
    h = {v: float('inf') for v in extended}
    h[SRC] = 0

    for _ in range(len(extended) - 1):
        changed = False
        for u in extended:
            if h[u] == float('inf'):
                continue
            for v, w in extended[u]:
                if h[u] + w < h[v]:
                    h[v] = h[u] + w
                    changed = True
        if not changed:
            break

    # проверка отрицательного цикла
    for u in extended:
        if h[u] == float('inf'):
            continue
        for v, w in extended[u]:
            if h[u] + w < h[v]:
                raise ValueError('в графе есть отрицательный цикл')

    # 3. перевешиваем рёбра — все веса становятся неотрицательными
    reweighted = {
        u: [(v, w + h[u] - h[v]) for v, w in graph[u]]
        for u in graph
    }

    # 4. Дейкстра из каждой вершины
    result = {}
    for src in vertices:
        dist = {v: float('inf') for v in vertices}
        dist[src] = 0
        pq = [(0, src)]

        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue
            for v, w in reweighted[u]:
                if d + w < dist[v]:
                    dist[v] = d + w
                    heapq.heappush(pq, (dist[v], v))

        # 5. возвращаем настоящие расстояния
        result[src] = {
            v: (dist[v] - h[src] + h[v] if dist[v] != float('inf') else float('inf'))
            for v in vertices
        }

    return result


graph = {
    'a': [('b', -2)],
    'b': [('c', -1)],
    'c': [('a', 4), ('d', 2)],
    'd': [],
}

for src, dists in johnson(graph).items():
    print(src, dists)
# a {'a': 0, 'b': -2, 'c': -3, 'd': -1}
# b {'a': 3, 'b': 0, 'c': -1, 'd': 1}
# ...

Шаг 5 обязателен. Дейкстра посчитала расстояния в перевешенном графе, и их нужно вернуть к исходным, обратив формулу: настоящее = новое − h[src] + h[v].

Когда что выбирать

Практический ориентир: при E < V² / log V Джонсон выигрывает. На графе из 1000 вершин и 5000 рёбер разница с Флойдом составляет порядки.

Но у Флойда-Уоршелла есть свой козырь — три строки кода против нескольких десятков. При V до 300–400 его обычно и берут.

Частые ошибки

Забытое обратное преобразование. Расстояния останутся в перевешенном графе — числа будут выглядеть правдоподобно, но окажутся неверными.

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

Пропущенная проверка отрицательного цикла. При его наличии кратчайших путей не существует, а алгоритм молча выдаст мусор.

Дейкстра до перевешивания. Отрицательные веса нарушают её основное допущение — результат будет неверным.

Что запомнить

• Джонсон делает все веса неотрицательными, чтобы можно было применить Дейкстру.
• Перевешивание w' = w + h[u] − h[v] меняет все пути между парой вершин одинаково, поэтому кратчайшие сохраняются.
• Потенциалы берутся из Беллмана-Форда от фиктивного источника, соединённого со всеми вершинами.
• После Дейкстры расстояния обязательно нужно преобразовать обратно.
• Выгоден на разреженных графах; на плотных проще Флойд-Уоршелл.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→