Алгоритм Левита: между Дейкстре и Беллманом

Привет, Хабр! Когда заходет речь о поиске кратчайшего пути между двумя вершинами выбор обычно падает на Дейкстре или Беллмана-Форда, однако есть ещё один алгоритм, который может сработать быстрее Беллмана, но не "сломается" на графах с отрицательными рёбрами.

Приятного чтения!

1. Суть алгоритма

2. Код!

3. Сравнение с другими

4. Заключение

Суть алгоритма

Как работает Левит? В целом достаточно просто! У нас есть 3 структуры m0-m2, каждая из которых имеет свои функции.

• m0 - список вершин, до которых и до соседей которых мы уже рассчитали путь (но не факт, что окончательно).

• m1 - список (или в нашем случае удобнее будет дек) вершин, в котором находятся вершины, до которых мы можем дойти. Почему дек? Потому что так будет удобнее потом доставать вершины, когда нужен будет перерасчёт.

• m2 - список вершин, до которых мы ещё никак не добрались.

ВАЖНАЯ ОГОВОРКА! Использование одного дека для m1 не рекомендуется, согласно Викиконспектам такая реализация может вызвать проблемы с вычислениями. Более безопасно - две очереди m1: основная, в которую попадают из m2, и срочная, в которую попадают из m0 (надеюсь, что дальше будет понятнее). Продолжим.

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

Как только мы находим путь до вершины, до которой не знали как добраться, мы забираем её из m2 и помещаем в m1. Из m1 мы забираем вершину и считаем расстояние до её соседей. Тут возможны следующие варианты

• Мы нашли путь до вершины, до которой мы не знали пути раньше (то есть она у нас была в m2). Мы забираем её оттуда и записываем расстояние до неё и её "предков".

• Мы нашли более короткий путь до вершины, которая у нас уже в m1, то есть в очереди на обработку. Тогда мы просто переписываем расстояние до неё и меняем "предка".

• Мы нашли более короткий путь до вершины, которую уже обрабатывали, то есть она в m0. Это значит, что и до её соседей мы можем добраться быстрее, а значит надо забрать её из m0 и поместить в m1 на перерасчёт на первое место в очереди.

В остальных случаях мы ничего не делаем. Собственно в 3 пункте и кроется главное отличие от алгоритма Дейкстре, который может выдать неправильный ответ, если у нас будет ребро с отрицательный весом. А теперь код!

Код!

Подготовка

Начнём с представления графов. Для нас граф - это точки, связанные рёбрами, у которых есть веса. Значит будет достаточно просто создать класс, который будет хранить рёбра нашего графа в виде массива [откуда, куда, вес].

class Graph:
    def __init__(self, vertices:int) -> None:
        self.V = vertices
        self.graph = []

    def add_edge(self, u:int, v:int, w:int) -> None:
        self.graph.append([u, v, w])

И импортируем встроенный модуль Python - collections, чтобы взять из него deque.

import collections

Основная часть

Инициализируем 3 структуры и поместим в m1 стартовую вершину. Затем создадим массивы расстояний и родительских вершин, указывая значения для стартовой точки в них как 0 и None соответственно.

*gr - экземпляр класса Graph.

def levit(gr, start: int = 0) -> None:
    m0 = []
    m1 = collections.deque()
    m2 = [x for x in range(gr.V)]
    
    m1.append(m2.pop(start))

    dist = [float('inf') for _ in range(gr.V)]
    dist[start] = 0

    pred = [-1 for _ in range(gr.V)]
    pred[start] = None

Dist (distance) заполнили бесконечностью, чтобы понимать, что мы пока не рассчитывали к ним расстояние, а pred (predecessors) -1, так как по-умолчанию считаем, что названия вершин будут цифры от нуля или буквы.

Теперь сам цикл. Берём вершину, расстояние до соседей которой будем рассчитывать. Затем проходимся по всем рёбрам графа, находим нашу вершину, смотрим её соседей и выполняем простой алгоритм, описанный выше в теории.

while m1:
    current = m1.popleft()
    for u, v, w in gr.graph:
        if u == current:
            # мы не находили путь к этой вершине раньше
            if v in m2:
                dist[v] = dist[u] + w
                m2.remove(v)
                m1.append(v)
                pred[v] = u
            
            # мы уже знаем какой-то путь к ней, но не от неё
            elif v in m1:
                # нашли более короткий путь
                if dist[v] >= dist[u] + w:
                    dist[v] = dist[u] + w
                    pred[v] = u
            
            # мы уже посчитали путь от вершины v к её соседям
            elif v in m0:
                # нашли более короткий путь до вершины v
                if dist[v] > dist[u] + w:
                    dist[v] = dist[u] + w
                    pred[v] = u
                    # отправили вершину на перерасчёт всех путей к её соседям
                    m0.remove(v)
                    m1.appendleft(v)

    # расчёт путей до соседей окончен
    m0.append(current)
        

На этом мы закончили с Левитом, листинг всей программы с доп. комментариями для тех, кто пропустил куски, и перейдём к сравнению с двумя другими алгоритмами.

def levit(gr, start: int = 0) -> None:
    # вершины, расстояние до которых и сосдей которых посчитали
    m0 = []

    # вершины, расстояние до соседей которых надо рассчитать
    m1 = collections.deque()
    
    # вершины, до которых мы ещё не знаем, как добраться
    m2 = [x for x in range(gr.V)]
    m1.append(m2.pop(start))
    
    # массив расстояний до вершины
    dist = [float('inf') for _ in range(gr.V)]
    dist[start] = 0

    # родительские вершины
    pred = [-1 for _ in range(gr.V)]
    pred[start] = None

    while m1:
        current = m1.popleft()
        for u, v, w in gr.graph:
            if u == current:
                # мы не находили путь к этой вершине раньше
                if v in m2:
                    dist[v] = dist[u] + w
                    pred[v] = u
                    m2.remove(v)
                    m1.append(v)
                    
                # мы уже знаем какой-то путь к ней, но не от неё
                elif v in m1:
                    # нашли более короткий путь
                    if dist[v] >= dist[u] + w:
                        dist[v] = dist[u] + w
                        pred[v] = u
                
                # мы уже посчитали путь от вершины v к её соседям
                elif v in m0:
                    # нашли более короткий путь до вершины v
                    if dist[v] > dist[u] + w:
                        dist[v] = dist[u] + w
                        pred[v] = u
                        m0.remove(v)
                        # отправили вершину на перерасчёт всех путей к её соседям
                        m1.appendleft(v)

        # расчёт путей до соседей окончен
        m0.append(current)
        

Сравнение с другими

Однако понятно, что нет абсолютно идеального алгоритма для всего, иначе бы все использовали его, а про другие забыли. Так что в конце сравнение с Дейкстре и Беллманом в табличке, которая разделит их по кейсам применения.

Как мы видим Дейкстре является самым быстрым в плане выполнения из всех 3, однако в определённом виде графы с отрицательными вершинами поломают его. Что же касается скорости выполнения Левита и Беллмана, то тут нужна оговорка, что Беллман-Форд выполняется фиксированное количество раз, после которого уже гарантировано найдены кратчайшие пути, а потом ещё 1 контрольный, в то время как Левит имеет шансы выполняться до скончания времён с бесконечным циклом, но обходит Беллмана при удачном раскладе.

Ну и чисто субъективно беллмана-форда проще написать.

Заключение

Как итог алгоритм Левита имеет в себе достаточно простую идею с перерасчётом, за счёт чего справляется с отрицательными рёбрами, а также в лучшем случае обгоняет Беллмана, но вместе с тем имеет риски бексонечного расчёта при наличие отрицательного цикла. Какой использовать - решать только программисту в зависимости от задачи.

Спасибо за прочтение, вот ещё ссылки на ресурсы:

Викиконспекты, если нужен более содержательный подход с кодом на C++.

Видео на русском для визуалов-аудиалов c кодом на Python.

Мой GitHub с этим и другими алгоритмами.