Ответ 1
- Моделируйте свою проблему как graph. Каждая станция будет Vertex, и каждый автобус/поезд будет Edge.
- создайте функцию
w:Edges->R, которая указывает время/деньги/... для каждого ребра. - теперь у вас типичная проблема с минимальным пути, которая может быть решена Dijkstra algorithm, который находит минимальный путь ко всем вершинам из данного источника.
(*) Для "наименее переходов" ваш вес фактически равен 1 для каждого края, поэтому вы можете даже оптимизировать его, запустив BFS или даже двунаправленный BFS вместо dijkstra, как я объяснил в этом post [Это объясняется для социальной дистанции, но на самом деле это тот же самый алгоритм].
ИЗМЕНИТЬ
Как изменение нестатического характера графика [по времени], которое вы упомянули в комментариях [для цены и количества переходов, то, что я упомянул выше, все еще применяется, поскольку эти графики являются статическими], вы можете использовать алгоритм маршрутизации вектора расстояния, который на самом деле предназначен для работы с динамическими графами и является распределенным изменением Алгоритм Беллмана Форда.
Идея алгоритма:
- периодически каждая вершина отправляет свой "вектор расстояний" в свою соседи [вектор указывает, сколько это "стоит" для перемещения из отправляющей вершины, к каждой другой вершине.
- Соседи пытаются обновить свои таблицы маршрутизации [через какой край лучше всего перейти к каждой цели]
- для вашего случая, каждый node знает, что является самым быстрым способом добраться до его соседей, [время в пути + время ожидания], и [[vertex/station] добавляет этот номер к каждому входу в векторе расстояния, в чтобы узнать, как и сколько времени потребуется, чтобы добраться до места назначения. Когда автобус уходит, время поездки должно быть пересчитано всем узлам [из этого источника], а новый вектор должен быть отправлен его соседям.