27
правок
Изменения
Нет описания правки
# <tex>M_1^{''}</tex> {{---}} срочная очередь;
* <tex>M_2</tex> {{---}} вершины, расстояние до которых еще не вычислено.
Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex> (в любую из очередей).
== Псевдокод ==
Для хранения вершин используем следующие структуры данных:
* <tex>M_0</tex> {{---}} хэш-сет,
* <tex>M_1</tex> {{---}} основная и срочная [[Очередь|очереди]],
* <tex>M_2</tex> {{---}} хэш-сет.
'''for''' <tex>u : u \in V</tex>
В плохих случаях алгоритм Левита работает за экспоненциальное время. Рассмотрим граф с <tex>3n</tex> вершинами и такими рёбрами:
* ребро <tex>(1,</tex> <tex>2n + 1)</tex> веса <tex>2^{n/2}</tex>,
* для нечётных вершин <tex>i</tex> : <tex>2 \cdot n2n+1 \leqslant i \leqslant 3n</tex> идёт ребро <tex>(i,i+2)</tex> веса <tex>2^{(3n-i)/2}</tex>,
* для вершин <tex>i</tex>: <tex>1 \leqslant i < 3n</tex> идёт ребро <tex>(i,i+1)</tex> веса <tex>0</tex>.
Ясно, что кратчайший путь до каждой вершины равен <tex>0</tex>, но в плохом случае алгоритм будет часто пересчитывать последние вершины. На 1 шаге в очередь положат две вершины: с номером <tex>2</tex> (после нескольких шагов вершинам от <tex>2</tex> до <tex>2n + 1</tex> алгоритм сделает веса равными <tex>0</tex>) и с номером <tex>2n + 1</tex> (через такое же число шагов вершинам от <tex>2n + 2</tex> до <tex>3n</tex> будет задан вес <tex>2^{n/2}</tex>). Оставшиеся <tex>n-2</tex> вершины находятся , находящиеся в очереди <tex>M_0</tex>, алгоритм начнёт образуют последовательность маленьких циклов длины <tex>3</tex>, в которых два ребра нулевого веса. Каждый такой цикл увеличит количество добавлений следующих двух вершин в <tex>M_1{''}</tex> на <tex>1</tex>. Алгоритм будет часто пересчитывать их весрасстояние до последних вершин, что приведёт к так как их многократному добавлению часто добавляли в <tex>M_1{''}</tex>, что даёт экспоненциальное время. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим уступает алгоритму [[Алгоритм Дейкстры|Дейкстры]].
==См. также==
