Не так давно я писал статью, в которой я описывал данный алгоритм. После серии доработок, благодаря идее Narg появилась более хорошая версия данного алгоритма. Ниже излагаю ее, без доказательств(доказательства найдете в предыдущей версии).
Шаг 1. Произведем конденсацию графа. Если в компоненте связности есть цикл отрицательного веса - значит, в этой компоненте связности из любой вершины можно добраться в саму себя по неограниченно малому пути. Помечаем все вершины этой компоненты черным цветом. Если же в компоненте нет такой вершины - помечаем все ее вершины белым цветом.
Шаг 2. Запускаемся из каждой вершины 0-1 обходом.
Собственно, вот обновленная версия алгоритма.
Недавно я заинтересовался, насколько медленно/быстро работает мой алгоритм в сравнении с алгоритмом Флойда. Я взял код Эдварда Давтяна и протестировал его Флойд и мой алгоритм(генератор тестов). Тестирование проводилось на почти полных, разреженных в 4 раза и на разреженных в 20 раз графах. Результат превзошел все мои ожидания:
| n | m | тип ребер(все положительные +, если есть отрицательные -) | время работы Флойда, мс | время работы моего алгоритма, мс |
| 100 | 9000 | + | 38 | 36 |
| 100 | 9000 | - | 48 | 68 |
| 200 | 39000 | + | 263 | 160 |
| 200 | 39000 | - | 280 | 513 |
| 400 | 159000 | + | 2080 | 1224 |
| 400 | 159000 | - | 2033 | 4054 |
| 500 | 240000 | + | 4043 | 2336 |
| 500 | 240000 | - | 3880 | 7482 |
| 100 | 2500 | + | 31 | 93 |
| 100 | 2500 | - | 47 | 110 |
| 200 | 10000 | + | 265 | 125 |
| 200 | 10000 | - | 276 | 226 |
| 400 | 40000 | + | 2068 | 409 |
| 400 | 40000 | - | 2028 | 1096 |
| 500 | 62500 | + | 4027 | 701 |
| 500 | 62500 | - | 3861 | 2019 |
| 100 | 500 | + | 29 | 93 |
| 100 | 500 | - | 37 | 94 |
| 200 | 2000 | + | 237 | 105 |
| 200 | 2000 | - | 265 | 120 |
| 400 | 8000 | + | 1968 | 180 |
| 400 | 8000 | - | 1954 | 305 |
| 500 | 12500 | + | 3902 | 251 |
| 500 | 12500 | - | 3766 | 492 |
n
m
тип ребер(все положительные +, если есть отрицательные -)
время работы Флойда, мс
время работы Вашего алгоритма, мс
400
159000
-
2033
4054
500
240000
-
3880
7482
Собственно они, наверное, ставят пока под вопрос и его эффективность...
BPSW тоже 250 строк кода вместо проверки за корень на 3 строки. Укконен тоже 100500 строк кода. И вот че?
O(n3) и O(n * m) - это как ложка и вилка. Иногда лучше одно, иногда другое, но по сути одна фигня.
решать задачикушать.JKeeJ1e30 суров! JKeeJ1e30 не страшит гиря!
- Инициализация
- Считывание
- Флойд в 4 строки
- Флойд в 4 строки
- Восстановление ответа
- Вывод
- Куча требухи (#include и т.д.)
Идейных строки то всё-равно 2 по 4 =Dа, ну конечно такого кода...
кстати, я не пойму смысла вот этого:
if (old[i][j] == d[i][j] && d[i][j] > -INF64 / 2)
{
;
}
это шикарно)
Блин, я просто взял готовый код Эдика и чуть-чуть его поправил под свои нужды. Пустой оператор времени много не отнимает, ведь так? Хорош по мелочам придираться.
Вот еще такая таблица. Понятное дело, сравнения с Флойдом нет, потому что на таких тестах Флойд до завтра не отработает.
Векторы на массивы поменять попробуй, ускориться же должно. (хотя вряд ли сильно)
заменить на 3 обычных массива. Правда, обход будет в пару строк длиннее.
Иногда такая замена изменяет вердикт с TL на AC.
Если кратко, то он битово сжимает булены и из-за этого имеет ряд спецэффектов. Короче, не нужен в 99% случаев. Заодно известен как эпик фейл стандартизации в STL.
в смысле, ты столько времени занимаешься этим алгоритмом, зачем? у тебя лаба? просто интересно? хочешь придумать новый алго?
P.S. при чем тут кокосы?
Мне интересно и я хочу придумать новый алгоритм. Я его уже придумал, вопрос насколько полезным я его смогу сделать.
Описано в предыдущей статье. Из всех известных мне-только Флойд-Уоршелл, работающий за O(n3)
Для поиска у китайцев луше всего использовать их поисковик. Итак загружаем: http://baidu.com и в строке поиска вводим интересующий Вас алгоритм (естественно, на английском языке).
Проверено неоднократно - выгребает не только "и мох и болото", но попадаются и очень и даже очень стоящие вещи! :)
"и мох и болото" = байду :)
Вроде как вот тут http://solab.kaist.ac.kr/files/seminar/1st/All-Pairs%20Shortest%20Paths%20and%20the%20essential%20subgraph.pdf обещают за O(ns + n2logn) , где s=o(m) (s - подмножество ребер)
Спасибо, плохо искал значит:) Но у меня нет добавочной асимптотики, везде O(n*m). Предыдущий вариант решения был O(n1*m1 + n2*n2), где n1,n2 = O(n), m1 = O(m), но от такого варианта решения отказался - тормозное было ужасно.
Насчет добавочной асимптотики: реальное время этого алгоритма при небольших n (ну например n <= 10^7) может быть значительно меньше твоего. Наверное теперь следует сравнивать уже с данным алгоритмом, а не с флойдом :)
Если бы достать реализацию данного алгоритма...
Фигасе небольшие n. 107. Ты сам-то посмотри что ты написал.
Надо же как все просто. По твоей логике тогда вообще и с флойдом можно было не тестить, там же очевидно какая константа. Ты ведь даже алгоритм не вкуривал, это может быть оценка сверху или еще чего, и по секрету: константа иногда бывает < 1.