Алгоритм поиска ближайшего способа добраться от точки A до точки B в транзитной сети?

Question

Хорошо, я пытаюсь закодировать базовую программу, которая может помочь пользователю найти самый близкий путь к переходу из точки A в точку B в сети метро. В настоящее время я кодирую это на Java, и у меня есть три класса, которые являются классом Station, Route class и Control Class. Идея состоит в том, что объект Route хранит ограниченное количество объектов Station в списке массивов, который фактически имитирует один маршрут метро, ​​который содержит точное количество станций. Кроме того, объект Station, который может хранить несколько объектов маршрута, а также как станция транзитного метро, ​​расположенная на нескольких маршрутах одновременно. Часть, над которой я работаю, - это позволить пользователю войти в свою станцию ​​отправления и станцию ​​назначения, тогда программа распечатает список станций, которые им необходимо перенести (который должен быть как можно более низким), чтобы прибыть в их место назначения. В это время я довольно сильно ударил по поиску хорошего алгоритма для выполнения этой части программы, и я не могу понять, как написать код, который может выполнять эту задачу в сложной сети. Поэтому, если у кого-нибудь есть идеи, пожалуйста, помогите мне в этом. Спасибо.

Answer 1

Dijsktra's Algorithm хорошо подходит для расчета кратчайших путей одного источника на лету. Вы также можете заранее заранее скопировать все кратчайшие пути для каждой пары станций, используя алгоритм кратчайшего пути с несколькими источниками, например Floyd-Warshall Method.

Оба алгоритма очень просты в реализации, учитывая правильные структуры данных (я бы подумал, что класс маршрута, который у вас есть, может быть не нужен, почему бы вам просто не иметь, чтобы каждый объект станции содержал список его прямых соседей? внимательно следит за общей структурой данных графа). Вы могли бы создать предварительно вычисленную таблицу поиска (хотя для многих станций это было бы большим) для каждой станции, которая сообщает вам с этой станции, учитывая желаемую станцию ​​назначения, какую соседнюю станцию ​​переместится на следующую. Это было бы по существу создание routing tables для каждой станции.