java - 地下最短路径 - Java

Question

所以我想编写一个程序来查找 2 个火车站之间的最短路径。您建议什么是表示火车线路的最佳方式，它们在哪里相交并搜索？我目前的想法是邻接矩阵或列表，但我不确定，因为并非所有相邻点都链接。

例如。火车线路看起来像这样:

• 灰线站 - 滑铁卢、南华克、伦敦桥
• 黑线车站 - Kennington、Oval、Borough、London Bridge
• 黑线 2 站 - Kennington、Waterloo、Embankment
• Brown Line 站 - Elephant & CaSTLe、Waterloo、Embankment。

例如，如果我想从 Oval 到 Southwark，我会去:

• Oval 到 Black Line 上的 Kennington(然后切换 Blank line 2)
• 肯宁顿到滑铁卢(然后切换到灰线)
• 从滑铁卢到南华克。

Answer 1

这是一个最短路径问题。由于您对最短时间感兴趣，因此只需使用持续时间代替距离。 Dijkstra 算法是解决此类问题的常用方法。它在 Internet 上有详细记录。如果您打算生成所有行程的时间表，那么您应该研究 Floyd-Warshall 算法，因为它可以为所有站点对生成解决方案。

这两种方法都需要您将铁路系统建模为图表。边缘权重将是在站点之间行进的时间。对于有多条线路的车站，您可以使用多个节点和边缘，它们之间的权重为 4。