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

[Cvazimodo]

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

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

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

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

[Cvazimodo]

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

[iNils]

http://algolist.manual.ru/maths/graphs/shortpath/wave.php

[Nirth]

хм
http://www.google.com/search?hl=en&q=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B+%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0+%D0%BF%D1%83%D1%82%D0%B8&btnG=Search&lr=lang_ru

[iNils]

хм
http://www.google.com/search?hl=en&q=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B+%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0+%D0%BF%D1%83%D1%82%D0%B8&btnG=Search&lr=lang_ru
Видимо это не новое :) А при чем тут флейм?

[Cvazimodo]

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

[Cvazimodo]

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

[iNils]

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

[Cvazimodo]

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

[Usnul]

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


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

[Cvazimodo]

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


Если интересует давай мыло - вышлю код.

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

[666]

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

[valvika]

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