Как хранить схему метро?

Question

[EvgenySManko]

Доброго времени суток, дамы и господа.

Решил написать приложение-навигатор по подземке. Вот только ума не приложу, как хранить все эти станции с переходами между ними и связями. Есть какие-нибудь идеи?

Заранее большое спасибо.

Answer 1

[coderisimo]

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

Comments

[EvgenySManko]

а как искать маршрут до нужной станции?

[Артём Токаревских]

Графы, Breadth-First Search

[coderisimo]

из пункта А в пункт Б . Берете А проверяете ее братьев (нет ли среди них Б). потом ближайшие станции на тот же предмет , потом братьев ближайших станций, потом ближайшие станции ближайших станций итд )))))))) задача творческая. Когда обнаружите Б - маршрут найден. Но надо будет еще посчитать сколько шагов между А и Б , выбрать оптимальный маршрут. Так же можно использовать признак одной ветки (кольцо - частый ее случай) и искать маршрут в первую очередь используя его. Тут много нюансов.

[EvgenySManko]

coderisimo: спасибо!)

[coderisimo]

не за что! может быть это пригодится - www.vogella.com/tutorials/JavaAlgorithmsDijkstra/a... или просто погуглите "graph shortest path "

Answer 2

[riot26]

графы

Answer 3

[Alexej Simakov]

Вот хорошая книженция: Goodrich/Tamassia "Data Structures and Algorithms in Java", рекомендую.