Структура данных для железнодорожных маршрутов

Question

Какова хорошая структура данных для железнодорожных маршрутов. У меня есть информация обо всех поездах, через какие станции они проходят. Учитывая две станции, мне нужно придумать все возможные пути.

Я придумал график, где ключ - это начальная станция, а список смежности - это станции, через которые он проходит.

Но я думаю, что это не даст мне правильного ответа.

Answer 1

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

То есть иметь узел графа для каждой станции с ребрамипредставляющих железнодорожные сообщения между ними.

Затем возникает проблема поиска в графе, для которого существует множество алгоритмов на выбор.

Answer 2

Во-первых, у вас есть сеть железных дорог: это очень естественно выражается в том, что станции являются узлами на графике, а железнодорожные линии - это ребра, которые соединяют узлы.

Во-вторых, у вас есть поезда или, иначе говоря, линии. Это наиболее естественным образом выражается в виде набора путей через вышеприведенный график, каждый путь соответствует отдельному поезду.

Я предполагаю, что вам нужны все возможные маршруты в виде

Сесть на поезд T1 на станции S0, доехать до станции S1, переключиться на поезд T2, доехать до S2 и т. Д. ... прибыть в пункт назначения.

В таком случае я бы смоделировал как железнодорожную сеть, так и поезда в единой многографной структуре, с несколькими ребрами, ведущими от станции Sn к станции Sm, каждый из которых соответствует разному поезду, который проходит от Sn до Sm. Структура для этого будет набором узлов, каждый из которых имеет список исходящих ребер.

Затем выполните простой поиск в глубину, отметив отдельные ребра, чтобы убедиться, что вы не пересекаете ребро дважды, как в следующем псевдокоде генератора:

// path is a list of edges
// src,dst are nodes

procedure generate_route (path, src, dst)
  if src == dst
    yield path
  else
    for e in all outgoing edges of src
      if e is not visited
         mark e as visited
         generate_route (path + e, e.dst, dst)