Здравствуйте!

, ну, тема, конечно, заюзанная до ужаса, но не могли бы вы кто-нибудь дать мне НОРМАЛЬНЫЙ, ПОНЯТНЫЙ алгоритм, все какие-то странные. Если будет еще и исходник, да еще и на Паскале — это будет вообще круто.
Ну, задача такова: есть система путей дорожного сообщения, граф тобишь (без направлений и т.п., т.е. по одному пути можно и туды и сюды). Ну, множество вершин, соединенных вразнобой. Дано также 2 точки и надо найти наикратчайший по длине (не по числу вершин) путь из одной точки в другую. Еще бы и вывод результата — через какие вершины проходит этот путь.

Люди, очень-очень прошу, мне энто очень важно, плиз!!!

С уважением, Black_Silent.

Здравствуйте, Black_Silent, Вы писали:

В твоем случае лучше использовать алгоритм А* — он гораздо эффективнее при поиске путей из точки в точку (алгоритм Дейкстры ищет расстояния от одной до всех остальных).
Посмотри этот топик

Автор: dimzel
Дата: 25.02.03

, и здесь

Здравствуйте, Bell, Вы писали:

B>В твоем случае лучше использовать алгоритм А* — он гораздо эффективнее при поиске путей из точки в точку (алгоритм Дейкстры ищет расстояния от одной до всех остальных).
Не совсем верно. Во-первых, алгогритм Дейкстры перечисляет вершины в порядке
увеличения расстояния и не более того. Поэтому как только конечная вершна
будет перечислена, процесс нужно прервать. Во-вторых указанный A* алгоритм
настолько сильно похож на Дейкстру, что возникают легкие сомнения...

Вообще же поиск по достаточно большому количеству библиотек, влключая ACM,
IEEE и citeseer, ничего путного про этот алгоритм не дает, поэтому непонятно, сам ли автор придумал такой термин или он является стандратным в computer science.

B>Посмотри этот топик

Автор: dimzel
Дата: 25.02.03

, и здесь

Да, посмотреть действительно стоит, хотя замечание о Фибоначчиевых кучах
принимать буквально не стоит -- сколько я не старалася, но получить от них скорость,
хотя бы не меньшую, чем у обычных куч, не удавалось. Типичное отставание в 2-2.5 раза
на больших разреженных графах (V=10^6, E=20*V).

Вообще же, если скорость критична, то советую почитать интересную работу
Гольдберга "Shortest Path Algorithms: Engineering Aspects".

Здравствуйте, mab, Вы писали:

mab>Не совсем верно. Во-первых, алгогритм Дейкстры перечисляет вершины в порядке
mab>увеличения расстояния и не более того.

Да, согласен.

mab>Поэтому как только конечная вершна
mab>будет перечислена, процесс нужно прервать. Во-вторых указанный A* алгоритм
mab>настолько сильно похож на Дейкстру, что возникают легкие сомнения...

Я в свое время отбросил все сомнения после того, как получил выигрыш в 2-3 раза по сравнению с алгоритмом Дейкстры Хотя конечно многое зависит от затрат на вычисление эвристической функции.

mab>Вообще же поиск по достаточно большому количеству библиотек, влключая ACM,
mab>IEEE и citeseer, ничего путного про этот алгоритм не дает, поэтому непонятно, сам ли автор придумал такой термин или он является стандратным в computer science.