在最多包含两条红色边的图中找到最短路径

Question

问题是 ：

我知道我们应该将图形复制到 G1 和 G2 中，并且可能使用 Dijstra 的算法。我不确定我应该如何以一种方式连接 G1 和 G2，以便为这个问题找到正确的解决方案。

Answer 1

你几乎有了答案：

1. 再制作两个图形副本，因此您有 G、G1 和 G2。
2. 去除G2中的红色边，将G1中的每条红色边改为指向G2中对应的顶点而不是G1，将G中的每条红色边改为指向G1中对应的顶点。
3. 现在，每条有 2 条红色边的路径都以 G2 结束，所有有 2 条红色边的路径都以 G2 结束。类似地，所有具有 1 个红色边缘的路径都以 G1 结束。使用 Dijkstra 算法找到从 G 中的 s 到 G、G1 和 G2 中所有顶点的最短路径。
4. 对于 G 中的每个顶点，查看 G、G1 和 G2 中对应顶点的路径，取最短的一个，并将其平移回原始图。（因为少于 2 个红边的路径也是可以接受的）