Обсуждение:Алгоритм Левита

Откуда оценка на сложность? Здесь http://codeforces.ru/blog/entry/3793 проведено вполне убедительное исследование, которое показывает, что в худшем случае сложность экспоненциальная. 212.13.112.162 15:38, 2 марта 2013 (UTC)

Сложность

Сегодня закончил несколько тестов алгоритма Левита и Дейкстры Граф сильносвязанный, т.е. если представить себе матрицу, то вершинами графа будут ячейки, и каждая ячейка связана с соседними, причем в одну сторону один вес, например 0,8, а обратно - другой, например 1,4. (см. картинку)

пример сильносвязанного графа

Вот результат тестов (в секундах) [Windows7 x64, Core i5 4 ядра , Visual Studio 2010 Ultimate, приложение - win32]:

Кол-во вершин	Дейкстра	Левит
25650	0,008	0,333
90277	0,018	1,207
102600	0,022	1,423
124146	0,031	1,641
461838	0,133	7,608
786432	0,265	14,414

Поиск осуществлялся от 0-й вершины до всех остальных. Если построить график, то увидим линейную зависимость. Кстати в алгоритме Левита, приведенном на данном сайте, вместо q.push_front (to) надо поставить q.push_back(to) чтоб на таком графе не циклил. Парусов Валерий 04:11, 19 апреля 2015 (UTC)

Дуги с отрицательным весом

В первом же абзаце "Алгоритм также работает для графов с рёбрами отрицательного веса", но в формальной постановке задачи указано "Дан взвешенный ориентированный граф ${\displaystyle G(V,E)}$ без петель и дуг отрицательного веса" со сноской, что "Для графа с отрицательными весами применяется более общий алгоритм — Алгоритм Дейкстры с потенциалами".

Какому из утверждений верить?