Tag: 最短路径有

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

假设我们在一组顶点上有两个有向和正加权图（第一个图表示例如铁路，第二个表示公交车道;顶点是公交车站或铁路车站或两者）。 我们需要找到从A到B的最短路径，但我们不能将传输类型改为N次以上。 我试图修改Dijkstra的算法，但它只在一些“不那么平均和复杂”的图形上工作，我想我需要尝试不同的东西。 如何最好地表示“双图”以及如何管理遍历图表的有限数量的更改？ 是否有可能在这一个中适应Dijkstra的算法？ 任何想法和线索都会有所帮助。 编辑：我忘记了一件事（我认为这很重要）：N = 0,1,2，…; 我们可以得出我们喜欢的任何图形表示，当然每两个节点之间可以存在最多4条边（1个公交车道和1个铁路在一个方向上，1个公交车道和1个铁路在第二个方向）。