所以我想编写一个程序来查找两个火车站之间的最短路径。你认为最好用什么方法来表示铁路线，它们相交的地方，然后搜索这个?我目前的想法是邻接矩阵或列表，然而，我不确定，因为不是所有的邻接点都是链接的。
。火车线路应该是这样的:
- 灰线车站-滑铁卢，南华克，伦敦桥
- 黑线车站-肯宁顿，椭圆形，博罗，伦敦桥
- 黑线2站- Kennington, Waterloo, Embankment
- 棕色线车站-大象&;城堡，滑铁卢，河堤。
例如，如果我想从Oval到Southwark，我会输入:
- 椭圆到肯宁顿在黑线(然后切换空白线2)
- 肯宁顿至滑铁卢(然后转灰线)
- 滑铁卢到南华克。
这是一个最短路径问题。既然你对最短的时间感兴趣，那么就用持续时间来代替距离。Dijkstra算法是解决这类问题的常用方法。它在互联网上有很好的记录。如果你打算生成所有行程的时间表，那么你应该研究Floyd-Warshall算法，因为它可以生成所有对车站的解决方案。
这两种方法都需要您将铁路系统建模为图形。边权值将是在车站之间移动的时间。对于具有多条线路的站点，您可以使用多个节点和边缘，它们之间的权重为4。
这与旅行推销员问题类似，对于旅行推销员问题，除了尝试所有可能的路径之外，没有已知的封闭解。请注意，这种路径的数量随着站点的数量呈指数增长，因此它在计算上很快变得非常昂贵。
同时，你必须决定你是想要车站之间的最短距离，还是它们之间的最短旅行时间。