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

#алгоритм

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

Как организовать базу данных и выборку транспорта?
    

Ответы

Ответ 1

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



В зависимости от масштабов проекта и желаемого результата могу предложить вам следующие
варианты:


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




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

А что делать, если таких путей нужно несколько (чтобы пользователь мог выбрать удобный
для него)?


  
  Можно использовать 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


Ответ 2

Заведите себе гиперграф. Остановки - вершины, маршруты - ребра. Потом ищите пути
между вершинами (поиском в ширину, например).