5

我最近开始了一个项目，该项目涉及使用来自 London Ungerground 数据集的数据，以便找到距离给定车站 n 分钟的路线。

到目前为止，我已经能够解析数据集中的数据，并在每个站点之间创建可能的路线。我现在有一个具有以下属性的路由对象列表：

Parent - the first station
Child - the next linked station
Line - whichever line the station is on
Time - the time between the two stations

我目前拥有的数据，以 VICTORIA 作为起点站是：

我已经格式化了我的输出以使其更易于阅读，但每一行都是一个路由对象的表示。所以你有起始站、时间、下一站和线路。

VICTORIA => 1 <= PIMLICO : Victoria
VICTORIA => 2 <= GREEN PARK : Victoria
VICTORIA => 2 <= ST JAMES PARK : Circle
VICTORIA => 2 <= SLOANE SQUARE : Circle
PIMLICO => 2 <= VAUXHALL : Victoria
GREEN PARK => 2 <= OXFORD CIRCUS : Victoria
GREEN PARK => 1 <= WESTMINSTER : Jubilee
GREEN PARK => 2 <= BOND STREET : Jubilee
GREEN PARK => 1 <= PICCADILLY CIRCUS : Piccadilly
GREEN PARK => 1 <= HYDE PARK CORNER : Piccadilly
ST JAMES PARK => 1 <= WESTMINSTER : Circle
SLOANE SQUARE => 1 <= SOUTH KENSINGTON : Circle
VAUXHALL => 2 <= STOCKWELL : Victoria
VAUXHALL => 2 <= PIMLICO : Victoria
OXFORD CIRCUS => 1 <= PICCADILLY CIRCUS : Bakerloo
OXFORD CIRCUS => 2 <= REGENTS PARK : Bakerloo
OXFORD CIRCUS => 2 <= TOTTENHAM COURT ROAD : Central
OXFORD CIRCUS => 1 <= BOND STREET : Central
OXFORD CIRCUS => 2 <= GREEN PARK : Victoria
OXFORD CIRCUS => 1 <= WARREN STREET : Victoria

从维多利亚收集所有可能的路线的最佳方法是什么？

例如：

VICTORIA > GREEN PARK > WESTMINSTER
VICTORIA > GREEN PARK > BOND STREET
VICTORIA > PIMLICO > VAUXHALL
4

1 回答 1

12

听起来像一个图论问题。我的最爱！

找到“所有可能的路线”的问题在于，使用您提供的数据（或这种情况下的任何实际数据集），您将遇到循环。因此，对于任何给定的路线，您都需要确保每个站点只被访问一次。

由于您只有一个起点，我会推荐Djikstra 的 Alogrithm。这将找到一条从VICTORIA到其他所有车站的路径（实际上是最短路径） 。至少，每个其他可到达的站点。这是一种众所周知的、快速且相对容易实现的算法。正常运行在 O(n^2) 时间内，但可以通过一些数据结构 jimmying 按摩成 O(m + nlogn)。

希望这至少能让你走上正轨！

于 2013-07-02T12:10:48.330 回答