存在一个使我发疯的问题！
我有80个城市，还有另一个出发城市。我需要找到从一个城市到这80个城市中每一个的最短路径。但是问题是旅行者可能会使用公共汽车或火车。
在输入中，有关以下信息的信息：两个特定城市之间是否有火车；是否有通往特定城市之间的公交车道；使用这些选项之一的旅行者的平均旅行时间，以及之间的平均旅行时间提供城市中的公交车站和火车站（如果同时提供）。在前往特定城市的旅途中，我们最多只能更改一次交通方式。
我认为我可以将这个问题抽象为每个城市都是一个顶点，并且由于该结构可能不是非循环图；我可能会使用Bellman-Ford之类的算法或其他在O（V.E）时间运行的算法。但是，两个城市之间可能有2条边，一条是公共汽车，一条是火车。然后我不知道该如何处理。因此，递归将取决于2个参数，即指定的顶点和到达该城市的最大边数。但是在这里，我想我还有一个关于火车客车问题的参数，我不知道该如何处理，因为我说过我们可能在旅途中最多改变一次运输方式。
我担心的是，如果有两个城市可以在整个旅程中更改运输方式，那么由于成本较低而在第一个可能的城市中更改运输方式可能不会导致总成本最低，因为可能会更改运输方式在第二个可能的城市中，降低成本要比在第一个城市中降低的成本高。
任何帮助将不胜感激。预先感谢！
除了将每个城市和每个火车停靠在一个节点上之外，您还可以选择将每个公交车站和每个火车停靠在一个节点上，并且在相邻公交车站和相邻火车停靠站之间以及公交车站和火车停靠站之间具有边线相同的城市。然后，您可以运行某些SSSP算法，例如Dijkstra的算法，其运行速度比Bellman-Ford快得多，并且适用于源城市的非循环图（假设没有负边）。
为了确保您不会多次更改运输方式，您可以向每个州添加一个额外的布尔参数，以标记您之前是否曾经更改过运输方式。
假设您只有总线选项，为了解决此问题，您可以使用Dijkstra's algorithm，通常用于查找从单个节点到另一个节点的路径，但可以轻松修改以找到到所有节点的最短路径。图中的节点。我们确实将每个城市作为节点，将每个车道作为边缘，我们已经完成了：）
现在是有趣的部分，当您只能在火车和公共汽车之间切换一次时。让我们创建两个图Dijkstra's algorithm和G_b，其中G_t仅包含火车路径，G_t仅包含公交车路径，权重是行驶时间。下一步是使用一个有向边将G_b中的所有节点连接到G_b中的相应节点。创建此图的另一个副本，但是这次将G_t连接到G_t。
现在在这两个图形上运行G_b。如果您想知道哪个时间是到特定城市最短的时间，请从该城市的所有4次中最少地取时间。您可以通过检查图表中的图层是否更改来了解我们是否更改了交通方式。
由于我们只运行了Dijkstra算法两次，所以时间复杂度远低于Bellman-Ford。 Dijkstra's algorithm