“双图”中变化次数有限的最短路径

假设我们在一组顶点上有两个有向正权图（第一个图代表铁路，第二个图代表公交车道；顶点是公交车站或火车站或两者）。我们需要找到从 A 到 B 的最短路径，但我们不能改变交通工具类型超过 N 次。

我试图修改 Dijkstra 算法，但它只适用于一些“不那么简单和复杂”的图表，我认为我需要尝试一些不同的东西。

如何最好地表示“双图”以及如何管理遍历图时的有限变化？是否有可能在这个算法中采用 Dijkstra 算法？任何想法和线索都会有所帮助。

Edit:好吧，我忘记了一件事（我认为这很重要）：N = 0,1,2,...;我们可以想出任何我们喜欢的图形表示形式，当然，每两个节点之间最多可以存在 4 条边（一个方向上有 1 个公交车道和 1 个铁路，第二个方向上有 1 个公交车道和 1 个铁路）。

我认为这不是最好的方法，但您可以按如下方式创建节点：

Node:(NodeId, GraphId, correspondenceLeftCount)

（节点总数为number_of_initial_nodes * number_of_graphs * number_of_correspondences_allowed)

So:

对于边在哪里GraphId没有改变，correspondenceLeftCount也没有改变。 您添加新的 Edge 进行通信：

(NodeId, Graph1, correspondenceLeftCount)-> (NodeId, Graph2, 对应LeftCount - 1)`

对于请求 A->B： 你的起点是(A, graph1, maxCorrespondenceLeftCount) and (A, graph2, maxCorrespondenceLeftCount).
你的终点是(B, graph1, 0), ... , (B, graph1, maxCorrespondenceLeftCount), (B, graph2, 0), ... , (B, graph2, maxCorrespondenceLeftCount).

所以你可能需要调整你的 Dijkstra 实现结束条件，并且能够插入多个起点。