Обсуждение:Алгоритм Левита
Откуда оценка на сложность? Здесь 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)
Дуги с отрицательным весом
[править код]В первом же абзаце "Алгоритм также работает для графов с рёбрами отрицательного веса", но в формальной постановке задачи указано "Дан взвешенный ориентированный граф без петель и дуг отрицательного веса" со сноской, что "Для графа с отрицательными весами применяется более общий алгоритм — Алгоритм Дейкстры с потенциалами".
Какому из утверждений верить?