问题描述
问题是：我知道我们应该将图形复制到G1和G2中，并可能使用Dijstra算法。我不确定我应该如何将G1和G2联系起来，这样我才能获得此问题的正确解决方案。
推荐答案
您几乎得到了答案：
再复制两份图表，这样就有了G、G1和G2。 删除G2中的红色边，将G1中的每条红色边更改为指向G2中的对应顶点，而不是G1，并将G中的每条红色边更改为指向G1中的相应顶点。 现在，每条有两条红边的路径在G2中结束，所有有两条红边的路径在G2中结束。类似地，所有有1条红色边的路径都以G1结尾。使用Dijkstra算法找出从G中的s到G、G1和G2中的所有顶点的最短路径。 对于G中的每个顶点，查看到G、G1和G2中相应顶点的路径，取最短的一个，并将其转换回原始图。(因为红边少于2条的路径也可以接受)