Как организовать скрипт “откуда и куда”?

Сначала выбираем первый пункт "Откуда" (остановка городского транспорта), далее выбираем "Куда" (тоже остановка городского транспорта), и скрипт показывает все возможные маршруты, на которых можно до этого пункта добраться (трамваи, троллейбусы, маршрутные такси...). И еще показывает примечание, в котором указаны маршруты, на которых можно добраться с пересадками.
Как организовать базу данных и выборку транспорта?

Ответ

Можно обойтись любой стратегией поиска на графе, составленном из остановок и маршрутов (добавляя, например, фиктивные ребра на пересадки и на дорогу пешком).

В зависимости от масштабов проекта и желаемого результата могу предложить вам следующие варианты:
Поиск с помощью одно- и двунаправленного алгоритма Дейкстры (часто слабо не подходит для production'a, поскольку требует обхода большого числа ненужных вершин). Поиск с помощью одно- и двунаправленного алгоритма A* (или его вариаций типа Theta*). Обычно представляет собой лучшее решение для production'a по соотношению скорость / сложность реализации. Нужно твикать эвристику. Решения промышленного масштаба с препроцессингом, позволяющие находить ответ за миллисекунды. Рекомендую презентации и статьи Andrew Goldberg, который провел обзоры наиболее современных алгоритмов и эвристик для данной задачи, известных под аббревиатурами RE, HH, CH, TN, HL. Ссылки вы найдете в конце ответа. alt text http://i036.radikal.ru/1202/c7/eed9966758bd.png

Минус всех предложенных выше алгоритмов заключается в том, что они находят только один кратчайший путь.
А что делать, если таких путей нужно несколько (чтобы пользователь мог выбрать удобный для него)?
Можно использовать A* с различными эвристиками (практичное решение, сочетающее возможность настраивать эвристики с преимуществами исходного алгоритма). Воспользоваться алгоритмом Йена для нахождения k кратчайших путей на графе. Использовать любой альтернативный алгоритм поиска k кратчайших путей (обычно они менее известны, нежели алгоритм Йена), например, вот этот. Лично я не знаю алгоритмов, решающих задачу нахождения k кратчайших путей с массивным препроцессингом, однако, я не могу гарантировать, что на данный момент по этой теме нет толковых публикаций.

Презентации и дополнительные материалы по теме:
Andrew V. Goldberg - Routing Algorithms and Related Technology Andrew V. Goldberg - Hub Labeling Algorithm Andrew V. Goldberg - Shortest Paths in Road Networks Point-to-Point Shortest Path Algorithms with Preprocessing