具有有限数量变化的“双图”中的最短路径
假设我们在一组顶点上有两个有向和正加权图（第一个图表示例如铁路，第二个表示公交车道;顶点是公交车站或铁路车站或两者）。 我们需要找到从A到B的最短路径，但我们不能将传输类型改为N次以上。
我试图修改Dijkstra的算法，但它只在一些“不那么平均和复杂”的图形上工作，我想我需要尝试不同的东西。
如何最好地表示“双图”以及如何管理遍历图表的有限数量的更改？ 是否有可能在这一个中适应Dijkstra的算法？ 任何想法和线索都会有所帮助。
编辑：我忘记了一件事（我认为这很重要）：N = 0,1,2，…; 我们可以得出我们喜欢的任何图形表示，当然每两个节点之间可以存在最多4条边（1个公交车道和1个铁路在一个方向上，1个公交车道和1个铁路在第二个方向）。
我不认为这是最好的方法，但您可以按如下方式创建节点：
Node:(NodeId, GraphId, correspondenceLeftCount) （节点总数将为number_of_initial_nodes * number_of_graphs * number_of_correspondences_allowed ）
所以：
对于GraphId没有改变的边缘， GraphId也不会改变。 您添加了一个新的Edge用于对应：
(NodeId, Graph1, correspondenceLeftCount) – >（NodeId，Graph2，correspondenceLeftCount – 1）`
对于请求A-> B：您的起点是(A, graph1, maxCorrespondenceLeftCount)和(A, graph2, maxCorrespondenceLeftCount) 。
你的终点是(B, graph1, 0) ，……， (B, graph1, maxCorrespondenceLeftCount) ， (B, graph2, 0) ，……， (B, graph2, maxCorrespondenceLeftCount) 。
因此，您可能必须根据最终条件调整Dijkstra实现，并能够插入多个起点。