Романовский И.В.

Алгоритм Левита

Источник:
  Романовский И.В. Дискретный анализ: Учебное пособие для студентов, специализирующихся на прикладной математике и информатике. — 3-е изд., перераб. и доп. — СПб.: Невский Диалект; БХВ-Петербург, 2003. - с.221-222

<…> Состояние вычислительного процесса. Все множество вершин М разбивается на три подмножества:

М0 - вершины, расстояние до которых уже вычислено,

М1 - вершины, расстояние до которых вычисляется,

М2 - вершины, расстояние до которых еще не вычислялось.

Попадание вершины в множество М1 может быть неокончательным. Элементы, входящие в множество М1, делятся на два упорядоченных подмножества М11 и М12. Множество М11 назовем основной очередью, множество М12-срочной очередью.

Начальное состояние. Множества М0 и М12 пусты, множество М11 Состоит из элемента i-, множество М2 – из остальных вершин.

Стандартный шаг. Выбирается элемент i1 для перевода из М1 в М0. Если множество М12 не пусто, берется очередной элемент из него, если пусто-очередной элемент из М11. Вершина i1 переводится в M0 и просматриваются дуги, выходящие из нее. Рассмотрим дугу u и ее конечную вершину i2.

Если i2єМ2, то вершина i2 переводится из М2 в М1 (точнее, в конец очереди М11), причем ей сопоставляется значение

v(i2)=l(u)+v(i1).

Если i2єМ1, то текущее значение v(i2) сравнивается с l(u)+v(i1) и полагается равным меньшему из них. При этом вершина никак не передвигается в очереди.

Если i2єМ0 и v(i2)>l(u)+v(i1), то вершина i2 получает новое значение

v(i2):=l[u]+v[i1]

и возвращается для повторной обработки в множество M1, на этот раз в срочную очередь M12.

<…>

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

Метод Левита обладает еще и тем преимуществом перед методом Дейкстры, что он применим в случае отрицательных длин дуг (ведь «длина дуги» - это просто название, которое дает нам полезные ассоциации с реальностью). Если считать, что значения l(u) не обязательно положительны, решение задачи о кратчайшем пути значительно усложняется.

Первая трудность в том, что теряется простое правило метода Дейкстры для определения окончательности вычисленного расстояния до конкретной дуги. Эта трудность, как мы увидим дальше, обходится, хотя и с некоторой потерей эффективности метода (приходится проверять все дуги, ведущие в данную вершину).

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

• Запретить включение в путь контуров, т.е. рассматривать только простые пути, но такой запрет делает задачу очень сложной.



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