|
|
Чтобы найти кратчайший путь програмно и без рекурсий надо сделать два волновых фронта.
0. Изначально в первый фронт помещаешь исходное положение.
1. Перебираешь все вершины рассматриваемого фронта:
1.1. В противоположный заносишь все те, в которые ты попадаешь из данной вершины (далее "достигнутые" вершины), причем записываешь в них информацию о данной (говоришь, откуда ты в них пришел).
1.2. Расстояение от источника до каждой достигнутой вершины вычисляется по формуле:
[расстояние от источника до данной вершины]+[расстояние от данной до достигнутой вершины].
1.3. Если достигнутая вершина "достигалась ранее", то обновляешь данные только в том случае, если расчитанное расстояние получилось короче того, что хранится. Также если новое расстояние для вершины не оптимально - не включаешь ее в новый волновой фронт.
2. Переключешь фронты: рассматриваемый фронт онуляешь (именно сам фронт, служебную информацию для каждой вершины нельзя удалять). Рассматриваемым делаешь толькочто заполнившийся фронт. Повторяешь действия 1-2 до тех пор пока рассматривемый фронт не пуст.
3. Обращаешься к вершине, в которую хотелось прийти. Если в ней нет данных о вершине из которой дошла "волна", то эта вершина не достижима. Если данные есть - то можно выстроить цепочку переходов - это и будет кратчайший маршрут.
вот.
|
|
E-mail: 
info@telesys.ru
