Минимальные пути в графах - нид хелп!

Собственно возник вопрос, не знает ли кто быстрого алгоритма нахождения минимального пути между двумя вершинами в графе?

Использовал Дейкстру - слишком долго работает, граф довольно большой, думаю будет больше 1000 вершин... (30 сек на П-4 1600!!!)

Видел быструю реализацию подобной задачи на http://ati.su/tc.php - вот и интересует практически та же задача.

Кто подскажет?

[Drakosha]

а сколько сторон? что-то слишком долго, Дейкстра работает O(logV(V+E))

to AleXXXSoft

А по подробнее о графе и весах сказать можешь?
Дело в том, как я знаю, алгоритм Дейкстры довольно эффективный алгоритм для нахождения кратчайшего пути с положительными весами (если веса не обязательно положительные, то алгоритмы предлагаемые в книгах ещё более медленные). Поэтому я считаю, что чтобы постоить более "шустрый" алгоритм нужно учитывать специфику задачи.

З.Ы. Возможно структуры данных выбраны не оптимальным образом для реализации алгоритма Дейкстры. Можешь попробовать реализовать алгоритм Дейкстры с использованием бинарных куч, а лучше с использованием куч Фибаначи.

З.З.Ы Имхо нам будет проще если увидим листинг проги и исходные данные.

[BC Scout]

Попробуй алгоритмы Флойда - иногда они быстрее чем а. Дейкстры.

http://www-unix.mcs.anl.gov/dbpp/text/node35.html

Сообщение от Drakosha

а сколько сторон? что-то слишком долго, Дейкстра работает O(logV(V+E))

сторон ОЧЕНЬ много.... представьте себе карту России со всеми ее дорогами...

P.S. Дейкстра, насколько я знаю, по времени O(n^3)

BC Scout:
Попробуй алгоритмы Флойда - иногда они быстрее чем а. Дейкстры.

насколько я понял из статьи, сложность по времени у него такая же как у Дейкстры.... я вчера его пробовал, но он у меня не сработал, оказалось в формуле ошибка была, сейчас попробую еще раз...

спробовал Флойда. В общем он же рассчитывает кратчайшие пути от всех ко всем, работает по времени дольше Дейкстра от одного к одному. Модифицировал Флойда, чтобы считать от одного ко всем... стал работать раз в 10 быстрее (т.е. как и Дейкстра), но! самого главного-то нет! минимальную длину маршрута я знаю, но пути нет

skiproff:
З.Ы. Возможно структуры данных выбраны не оптимальным образом для реализации алгоритма Дейкстры. Можешь попробовать реализовать алгоритм Дейкстры с использованием бинарных куч, а лучше с использованием куч Фибаначи.

язык PHP - вот в чем основная проблема т.е. делается все в лоб... ибо больше ничего не разрешают.... увы, Perl не знаю...
буду пробовать реализовать бинарную кучу самостоятельно

сделал нечто с помощью бинарной кучи для 1000 вершин, между 50% всех вершин есть связи, получил ускорение на 10 сек в лучшем случае и замедление почти в 2 раза в худшем случае... выкладываю исходники, может кто что подскажет...
жрёт памяти немерено!

не знаю, что и делать, в реальной дорожной сети будет больше 14 тысяч городов! Хотя дорог много меньше...

road.php - собственно программа
heap.php - функции для кучек

[Hex0gen]

AleXXXSoft:
В случае с картой России, обобщенный алгоритм Дейкстры ОЧЕНЬ не оптимален. Россия (как и любая страна) со всеми ее дорогами - это очень специфичный граф.
Ищи не алгоритм поиска кратчайшего пути в графе, а алгоритм поиска кратчайшего пути на плоскости.

Сообщение от Hex0gen

AleXXXSoft:
В случае с картой России, обобщенный алгоритм Дейкстры ОЧЕНЬ не оптимален. Россия (как и любая страна) со всеми ее дорогами - это очень специфичный граф.
Ищи не алгоритм поиска кратчайшего пути в графе, а алгоритм поиска кратчайшего пути на плоскости.

да вот блин ничего не нашел по расчету расстояний на плоскости... ну как-то же сделали люди?может есть еще какие алгоритмы? слышал про волновой.... но что-то не допер как его реализовать... может какие модификации?

to AleXXXSoft
Я php не знаю, так что если что я не понял необижайтесь.
Как я понял в проге считается, что граф полный. Для карты России это будет явно не так. Поэтому предлагаю улучшение программы:
1) Граф хранить не с помощью матрицы инциденции, а с помощью двух массивов.
Пусть A,B массивы рёбер ({A[ i ],B[ i ]} - ребра i=1,|U| U-множество ориентированных дуг). Т.е. ты каждое ребро заменяешь на две дуги. Сортируешь массивы А и B по значениям массива A. (т.е. теперь {A[ i ],B[ i ]} - ребра, и A[1]<=A[2]<=...<=A[|U|]). Потом вводишь новый массив F размера |I|+1 , где F[ i ]=min{j:i<=A[j]} например с помощью цикла:

for (val=0;i=0;i<=|U|;i++)
if (A[i]!=val) then {
for(j=val+1;j<A[i];j++) F[j]=A[i];
val=A[i];
}
F[|I|+1]=|U|+1;

Трудоёмкость этих операций O(2*n*log(2*n)). Но теперь все дуги, исходящие из вершины i, это {i,B[j]} j=F[ i ],F[i+1]-1. Т.е. теперь все исходящие дуги будут определяться за O(k), где k-количество исходящих дуг k<<|U|.

2) Насчёт куч скажу немного попозже, там вроде процедуру "подъёма" нужно огранизовать.

_________________________________
Продолжение:


Блин мною была допущена ошибка в куске программы.

Нужно строчку
F[|I|+1]=|U|+1;
заменить на
for (j=val+1;j<|I|+1;j++) F[j]=|U|+1;

Насчёт алгоритма с кучами, то, кажется, у Вас что-то неправильно реализовано:
Вы при нахождении возможности уменьшения расстояния (т.е. если "$l[$v]+$d[$v][$k]<$l[$k]). Забравываете элемент в кучу, при этом "старый" элемент остаётся. Оттого куча зря растёт и рассматривается одна и та же вершина по несколько раз (лишняя трата времени). Нужно, Имхо, делать следующим образом:
1) Если текущее значения расстояние до данной верщины бесконечность ( if $l[$v]==BIG), то уменьшаем это и запихиваем в кучу.
2) если нет, то уменьшаем значение данной вершины и продвигаем вверг в куче (если меньше предка, то делаем обмен и т.д.). При этом встаёт вопрос, где находится элемент $l[$v] в куче, который решается введением вспомогательного массива position (position[v] - индекс элемента к куче). И теперь при всех операциях нужно следить за position, но это добавляет одну операцию, что не увеличивает асимтотическую сложность.

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

skiproff:
Насчёт алгоритма с кучами, то, кажется, у Вас что-то неправильно реализовано:
Вы при нахождении возможности уменьшения расстояния (т.е. если "$l[$v]+$d[$v][$k]<$l[$k]). Забравываете элемент в кучу, при этом "старый" элемент остаётся. Оттого куча зря растёт и рассматривается одна и та же вершина по несколько раз (лишняя трата времени). Нужно, Имхо, делать следующим образом:
1) Если текущее значения расстояние до данной верщины бесконечность ( if $l[$v]==BIG), то уменьшаем это и запихиваем в кучу.
2) если нет, то уменьшаем значение данной вершины и продвигаем вверг в куче (если меньше предка, то делаем обмен и т.д.). При этом встаёт вопрос, где находится элемент $l[$v] в куче, который решается введением вспомогательного массива position (position[v] - индекс элемента к куче). И теперь при всех операциях нужно следить за position, но это добавляет одну операцию, что не увеличивает асимтотическую сложность.

попробовал что-то такое реализовать. Теперь все зацикливается и все...

Сообщение от AleXXXSoft

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

На всякий случай упомяну о подводном камешке. Я не зря писал о том, что нужно сначала ребро заменить на две дуги, поэтому Вам из базы нужно доставать рёбра (правильнее сказать дуги) два раза, сначана отсортированные по входящим, затем по исходящим вершинам дуг. Потом вариантов два:
1) Произвести их слияние. (как итерация в merge-sort)
2) Хранить четыре массива B1,F1,B2,F2.
Имхо, первый вариант лучше.

Сообщение от AleXXXSoft

попробовал что-то такое реализовать. Теперь все зацикливается и все

Имхо, где-то Вы баг допустили (с идейной точки зрения, же всё правильно вроде). Оттого исходники в студию, тогда, думаю, смогу Вам помочь. А так я не ясновидящий.

З.Ы. Как я писал с php я не встречался (этот случай не всчёт ). Оттого буду презнателен, если расскажете как называется и где найти интерпретатор для php и что-то вроде отладчика. Тогда, возможно, моя помощь будет существенней.

З.Ы.Ы

но нигде не могу найти алгоритм обновления элемента в куче... ну или удаления

.
Алгоритм подъёма (именно то, что Вам нужно) Вы же почти реализовали: при вставке элемента в кучу, Вы же сначала добавляете элемент в конец кучи, а потом осуществяете его подъём (в Вашем же исходнике так написано).
Алгоритм удаления: Уменьшаем ключ до минус бесконечности, осуществяем подъём и удаление минимального. Это так навскидку, но, думаю, можно что-нибудь пооптимальнее придумать (например, ставить последний элемент кучи на место удаляемого, а потом производить или подъём, или спуск.

З.З.З.Ы. В моём предыдущем посте надоело исправлять не точности. Здесь [i] воспринимается не как индекс массива, а как курсив. На всякий, случай имейте ввиду и не кидайте гнилыми помидорами ) .

исходники вложил, массивы пока не переделывал, собственно разбирался с кучей....

ковырялся с функциями кучи просто небольшими массивчиками - вроде они работают правильно (если, я, конечно, правильно понял алгоритмы из книжки, которые я там и реализовал)

насчет PHP - там все не так просто, по крайней мере дистрибутив ПХП можно найти тут: http://php.net/ - 5-ю версию не брать, использовать нужно CLI-версию
отладчиков для ПХП не встречал сам.... пользуюсь, блин, банальными print_r - распечатка переменных....

в принципе мне бы подошел готовый алгоритм на Перле или Си, он у меня даже есть реализован, но так как там повсеместно используются списки и прочие хитрости языков, я там вообще не допираю... в ПХП, увы, этого ничего нет, все делается "в тупую"... потому все готовые алгоритмы не катят...

Сообщение от Hex0gen

AleXXXSoft:
В случае с картой России, обобщенный алгоритм Дейкстры ОЧЕНЬ не оптимален. Россия (как и любая страна) со всеми ее дорогами - это очень специфичный граф.
Ищи не алгоритм поиска кратчайшего пути в графе, а алгоритм поиска кратчайшего пути на плоскости.

нету нигде.... все поисковики перерыл, нашел на английском теоретические размышления на эту тему... и не более того...

[RaZEr]

отладчиков для ПХП не встречал сам

Уж что-что, а для CLI версии отладчиков одним местом не съесть.

По теме: Учитывая что сама структура не сильно динамическая (дороги у нас пока не воруют ), то можно попробовать найти все пути пути и записать их в таблицу, из которой потом выбирать будет много быстрее, чем искать заново.

Сообщение от RaZEr

Уж что-что, а для CLI версии отладчиков одним местом не съесть.

По теме: Учитывая что сама структура не сильно динамическая (дороги у нас пока не воруют ), то можно попробовать найти все пути пути и записать их в таблицу, из которой потом выбирать будет много быстрее, чем искать заново.

ну я не пользовался и не интересовался как-то, обходился без них.

Насчет заранее сделанных расчетов, я уже думал об этом... 14 тысяч точек - города, хрен знает сколько ребер, нужно учесть все возможные пути от точки к точке - табличка будет ЧЕРЕЗЧУР великовата. Была мысль, и она еще жива, неким образом кешировать уже вычисленные пути.

А вот если считать все сразу - никаких ресурсов не хватит.... один путь моим алгоритмом считается по 20-30 сек.... собственно потому и зашел разговор о более быстром алгоритме.

to AleXXXSoft
А Вы на правильность (не только на скорость) программу проверяли. Имхо когда запихиваешь элемент в кучу нужно писать не
$r["data"]=$v;
а
$r["data"]=$k;

Сообщение от skiproff

to AleXXXSoft
А Вы на правильность (не только на скорость) программу проверяли. Имхо когда запихиваешь элемент в кучу нужно писать не
$r["data"]=$v;
а
$r["data"]=$k;

исправил, ничего не изменилось

хотя нет, считает, но долго. ОЧЕНЬ. дольше чем методом в лоб...

думаю что-то с алгоритмами и функциями кучи неправильно, кушает память снова...

Ну вот немного поправил. Работает сек. 6-8. На правильность не тестировал, на прожорливость к памяти тоже.

З.Ы. Нек. "новые", написанные Вами я не читал даже (извиняйте). Кажется, они даже не нужны.

_______________________
Добавлено:

Присоединяю немного поправленную версию.
При исполнении кот. видно, что основную часть времени отжирает генерация матрицы (24.3 против 6.43 после увеличения размера). Память отжирается на этапе генерации матрицы. Имхо это достойный задел, т.к. прога оперировака с 1500^2=2 250 000 рёбрами, а в реальной задаче дуг бедет 14 000*A, где A - среднее количество исходяцих рёбер из вершины (Имхо A<=20). {Здесь, я считаю, что будет применено, написанное мною улучшение связанное со способом хранения графа}

З.Ы. Чтобы узнать, что я поправил, достаточно воспользоваться прогами fc для dos\win и diff для unix (Ex. "fc /l <file1> <file2> >> <result>, результат сраврения будет в <result>)

З.З.Ы за правильность работы не отвечаю.

З.З.З.Ы.

Сообщение от Drakosha

Дейкстра работает O(logV(V+E))

Интересно, откуда такая оценка взялась. Пусть граф это чепь и возьмём крайние вершины в качестве исходных, тогда между ними один путь, он же следовательно будет и оптимальным. Длина его |U|, где U - множество дуг. Оттого сложность алгоритма (любого о нах. кратчаёшего пути) не как не меньше O(|U|) (причём тождественная функция растёт быстрее логарифма от любого полинома, в том числе и квадраного).

[Drakosha]

Оценка взялась из Кормена. Кроме того тут об етом говоритса:
http://algolist.manual.ru/forum/show...2840/Main/2679

Недеюсь поможет, хотя немного поздно