Изменения

При неправильной реализации алгоритма, используя вместо очередей <tex>M_1{''}</tex> и <tex>M_1{'}</tex> [[Персистентный дек|дек]] и добавляя вершины из <tex>M_0</tex> в начало дека, алгоритм в худшем случае будет работать за экспоненциальное время, так делать не рекомендуется. В плохих случаях алгоритм Левита работает за экспоненциальное время<tex>O(n^2m)</tex>. Рассмотрим полный граф <tex>K_n</tex> с <tex>3\cdot n</tex> вершинами и такими <tex>m</tex> рёбрами, идущими в [[Лексикографический порядок|лексикографическом порядке]]: от вершины * для всех вершин <tex>1 < i < j \leqslant n</tex> вес ребра <tex>(i,j) = j - i - 1</tex>, т.е. количество вершин между <tex>i</tex> и <tex>j</tex>; <tex>w_{i,i+1}=0</tex> до ,* ребро <tex>(1,n)</tex> ребро веса <tex>2^0</tex>,* для всех вершин <tex>1 < i < n</tex>вес ребра <tex>(1,i) = w_{1, цепь i+1} + i - 1</tex>; от <tex>1</tex> до <tex>i</tex> вершины расстояние равно <tex>\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>n+21</tex> из <tex>M_0</tex> больше не достанут.На следующем шаге добавлений не произойдёт, так как вершины больше <tex>2</tex> уже в очереди..На <tex>3</tex> шаге алгоритм улучшит расстояние до вершины <tex>2</tex> на <tex>1</tex> (что видно из веса рёбер <tex>(1,2)</tex> и <tex>(1,3 \cdot n)</tex>; вес , равных <tex>i\sum\limits_{k=1}^{n-2}k</tex>-ого звена и <tex>\sum\limits_{k=2}^{n-i2}k</tex>соответственно), а также цепь рёбер от так что её добавят в <tex>M_1{''}</tex> и обработают на <tex>4</tex> шаге (релаксаций не происходит). На следующем шаге из обычной очереди достанут вершину <tex>14</tex> , расстояние до неё, равное <tex>\sum\limits_{k=3 \cdot }^{n-2}k</tex> (вес каждого звена , на <tex>02</tex>). Ясноменьше, что кратчайший путь чем расстояние до каждой вершины равен <tex>02</tex> и <tex>3</tex>вершин. Их добавят в срочную очередь, но так как <tex>w_{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>2</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>i</tex> составит <tex>1 + \sum\limits_{k=1}^{n-i}k</tex>, а сумма всех добавлений примерно составит <tex>O(nm)</tex>. При обработке каждой вершины приходится обходить <tex>n-1</tex> ребер, что даёт экспоненциальное времяоценку <tex>O(n^2m)</tex>. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим уступает алгоритму [[Алгоритм Дейкстры|Дейкстры]].