Друзья, будьте бдительны!

Алгоритм Левита взятый с http://e-maxx.ru/algo/levit_algorithm работает в худшем случае за экспоненциальное время.

Для пояснения привожу код, который генерирует ацикличный граф без отрицательных ребер из 91 вершин и 121 ребра (а также перемешивает все ребра в случайном порядке), на котором код по ссылке выше делает более 1 000 000 добавлений в очередь.

const int M = 30;
const int W = (int)8e8;

void gen()
{
  for (int i = 0; i < M; i++) 
    g[i].push_back(make_pair(i + 1, 0));
  g[0].push_back(make_pair(M, W));
  n = M;

  for (int i = 0; i < M; i++) 
  {
    g[n].push_back(make_pair(n + 2, W >> i));
    g[n].push_back(make_pair(n + 1, 0));
    g[n + 1].push_back(make_pair(n + 2, 0));
    n += 2;
  }
  n++;
  for (int i = 0; i < n; i++) 
    random_shuffle(g[i].begin(), g[i].end());
}

Какие выводы отсюда я хочу сделать? Не добавляйте в начало очереди, вся проблема в этом! Люди, добавляющие в начало очереди, рискуют однажды доиграться и попасться на хорошие тесты.

Если же вы хотите, чтобы ваш Форд-Беллман работал быстро — пишите обычного Форд-Беллмана с очередью, т.е. добавляйте вершины всегда в конец очереди и следите за тем, чтобы каждая вершина хранилась в очереди не более чем в одном экземпляре. Почитать можно здесь: http://wcipeg.com/wiki/Shortest_Path_Faster_Algorithm

P.S. В правильном "Левите" (см., например, книжку И.В.Романовского, Дискретный Анализ) использовалось 2 очереди. Описанный там алгоритм и правда работает за O(VE). Но от "Форд-Беллмана с очередью" не отличается (улучшение не более чем в 2 раза).

UPD:

Только что услышал такой способ искать кратчайший путь в графе с отрицательными ребрами:

Берем Дейкстру с кучей и запускаем на графе с отрицательными ребрами (при этом всегда, когда расстояние до вершины улучшается, кладем ее в кучу) :-) Казалось бы, этот алгоритм просто просмотрит каждую вершину несколько раз. На самом деле, он тоже работает за экспоненциальное время. Идея теста: давайте превратим ребра веса W в цепочки из двух ребер — веса 2^k и (W — 2^k). Далее строим такой же тест, как показан выше.