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

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

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

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

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

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

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

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

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

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

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

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

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


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

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


Usnul, с удовольствием узнал бы новый быстрый алгоритм поиска. Но на самом деле пока не знаю, куда ЭТО можно применить (проект некомерческий, развлекаловка для преподов), но куда бы я его ни вставлю, буду указывать авторство и ссылку.
Мой email: khva7 (at) yandex.ru
*** (at) заменить на @ и пробелы не нужны (защищаемся от спама) :)

я делал это на flash в институте

http://mainmaps.com/spb/vit.html
Это еще одна реализация волнового алгоритма. Нужно сделать клики на любых двух белых с красным ободком кнопках ( розовые кнопки пока не активны ).