Изменения

При неправильной реализации алгоритма, используя вместо очередей <tex>M_1{''}</tex> и <tex>M_1{'}</tex> [[Персистентный дек|дек]] и добавляя вершины из <tex>M_0</tex> в начало дека, алгоритм в худшем случае будет работать за экспоненциальное время, так делать не рекомендуется. В плохих случаях алгоритм Левита работает за экспоненциальное время<tex>O(n^2m)</tex>. Рассмотрим полный граф с <tex>3nK_n</tex> вершинами и с такими рёбрами, идущими в [[Лексикографический порядок|лексикографическом порядке]]:* ребро для все вершин <tex>(1,< i < j \leqslant n</tex> вес ребра <tex>2n + (i,j) = j - i - 1)</tex> веса , т.е. количество вершин между <tex>2^{n/2}i</tex>,* для нечётных вершин и <tex>ij</tex> : ; <tex>2nw_{i,i+1 \leqslant i \leqslant 3n}=0</tex> идёт ,* ребро <tex>(i1,i+2n)</tex> веса <tex>2^{(3n-i)/2}0</tex>,* для всех вершин <tex>1 < i< n</tex>: вес ребра <tex>(1 \leqslant ,i) = w_{1,i+1} + i - 1</tex>; от < 3ntex>1</tex> идёт ребро до <tex>(i,i+1)</tex> веса вершины расстояние равно <tex>0\sum\limits_{k=i-1}^{n-2}k</tex>.Ясно, что кратчайший путь до каждой вершины равен <tex>0</tex>, но в плохом случае алгоритм при подсчёте вершины <tex>i</tex> будет часто пересчитывать последние все вершиныдо неё (кроме первой). На <tex>1 </tex> шаге в очередь положат две вершины: с номером от <tex>2</tex> (после нескольких шагов вершинам от до <tex>n</tex>, причём вершину <tex>1</tex> из <tex>M_0</tex> больше не достанут. На следующем шаге добавлений не произойдёт, так как вершины больше <tex>2</tex> до уже в очереди. На <tex>2n + 13</tex> шаге алгоритм сделает веса равными улучшит расстояние до вершины <tex>02</tex>) и с номером на <tex>2n + 1</tex> (через такое же число шагов вершинам от что видно из веса рёбер <tex>2n + (1,2)</tex> до и <tex>(1,3)</tex>, равных <tex>3n\sum\limits_{k=1}^{n-2}k</tex> будет задан вес и <tex>\sum\limits_{k=2}^{n-2}k</2tex> соответственно), так что её добавят в <tex>M_1{''}</tex>и обработают на <tex>4</tex> шаге (релаксаций не происходит). Оставшиеся На следующем шаге из обычной очереди достанут вершину <tex>4</tex>, расстояние до неё, равное <tex>\sum\limits_{k=3}^{n-2}k</tex> вершины, находящиеся на <tex>2</tex> меньше, чем расстояние до <tex>2</tex> и <tex>3</tex> вершин. Их добавят в очереди срочную очередь, но так как <tex>M_0w_{24}-1=w_{34}</tex>, образуют последовательность маленьких циклов длины то после подсчёта вершины <tex>3</tex>, в которых два ребра нулевого веса. Каждый такой цикл увеличит количество добавлений следующих двух вершин вершину <tex>2</tex> снова добавят в <tex>M_1{''}</tex> на . Затем дойдёт очередь до вершины <tex>5</tex>, что вызовет релаксацию предыдущих вершин <tex>2,3,4</tex>, затем прорелаксируют вершины <tex>2,3</tex>, и после вершина <tex>12</tex>. Алгоритм будет часто пересчитывать расстояние до последних Аналогично будут происходить релаксации всех вершинпри обработке вершины <tex>i</tex> из очереди <tex>M_0</tex>. Таким образом, так как их часто добавляли вершину <tex>i</tex> будут добавлять в срочную очередь <tex>n-i</tex> раз (добавление вершин из очереди <tex>M_2</tex> с номером больше <tex>i</tex>) <tex>+</tex> количество добавлений "старшей" вершины <tex>i+1</tex>. Количество добавлений вершины <tex>M_1i</tex> составит <tex>1 + \sum\limits_{k=1}^{''n-i}k</tex>, а сумма всех добавлений примерно составит <tex>O(nm)</tex>. При обработке каждой вершины приходится обходить <tex>n-1</tex> ребер, что даёт экспоненциальное времяоценку <tex>O(n^2m)</tex>. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим уступает алгоритму [[Алгоритм Дейкстры|Дейкстры]].