Алгоритм поиска кратчайшего пути

[Cvazimodo]

Есть проблема с определением кратчайшего пути на местности. Известные с университетских времён алгоритм "транспортной" задачи (через оценку вершин ориентированного графа) реализован во флэше, но тормозит

Видел пример (видео с экрана) аналогичной реализации, но без тормозов. Вот и мне захотелось сделать подобное.

Отсюда вопрос - может кто-то подскажет алгоритм поиска кратчайшего пути? Реализацию не нужно, сам всё сделаю. Но вот описательную часть малотормозного механизма было бы хорошо поиметь.

P.S.: Не знаю, разрешено ли вывешивать здесь ссылки на пробные работы чтобы показать, но вот попробую - http://vl.nn.ru/graf/test_graf.html
(170 КБ + загружаемая карта с сервака 50 КБ).

[Cvazimodo]

Забыл сказать - поисковиками (яндекс, гугл...) пользоваться умею, но они ничего нового не выдают.

[iNils]

http://algolist.manual.ru/maths/grap...tpath/wave.php

[Nirth]

хм
http://www.google.com/search?hl=en&q...rch&lr=lang_ru

[iNils]

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

хм
http://www.google.com/search?hl=en&q...rch&lr=lang_ru

Видимо это не новое А при чем тут флейм?

[Cvazimodo]

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

http://algolist.manual.ru/maths/grap...tpath/wave.php

К сожалению, именно этот алгоритм я и использовал (только в описании он назывался иначе).
Вот ссылка, показывающая расчеты (криво, коряво, но только для визуала).
http://vl.nn.ru/based_graf/test_graf.html

[Cvazimodo]

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

А при чем тут флейм?

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

[iNils]

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

К сожалению, именно этот алгоритм я и использовал (только в описании он назывался иначе).
Вот ссылка, показывающая расчеты (криво, коряво, но только для визуала).
http://vl.nn.ru/based_graf/test_graf.html

Вот еще реализация от Гранта Скинера

[Cvazimodo]

Ух! Быстро считает
Спасибо, iNils, за файл, буду разбираться в этом алгоритме, он действительно быстрый.

[Usnul]

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


ЗЫ:
опять же, если ты постишь мыло, я шлю тебе алгоритм, то с тебя указание авторства.