在最多包含两条红色边的图中找到最短路径
Find the shortest path in an graph containing at most two red edges
问题是：
我知道我们应该将图形复制到 G1 和 G2 中，并且可能使用 Dijstra 算法。我不确定我应该如何连接 G1 和 G2 才能得到这个问题的正确解决方案。
你差不多有答案了：
- 再复制两张图，得到 G、G1 和 G2。
- 去除G2中的红边，将G1中的每条红边改为指向G2中对应的顶点而不是G1中，将G中的每条红边指向G1中对应的顶点。
- 现在，每条有 2 个红色边的路径都在 G2 中结束，所有有 2 个红色边的路径都在 G2 中结束。类似地，所有具有 1 个红色边缘的路径最终都在 G1 中。使用 Dijkstra 算法找到从 G 中的 s 到 G、G1 和 G2 中所有顶点的最短路径。
- 对于G中的每个顶点，查看到G中相应顶点的路径，G1和G2，取最短的一个，并将其转换回原始图形。 （因为少于2条红边的路径也是可以接受的）
问题是：
我知道我们应该将图形复制到 G1 和 G2 中，并且可能使用 Dijstra 算法。我不确定我应该如何连接 G1 和 G2 才能得到这个问题的正确解决方案。
你差不多有答案了：
- 再复制两张图，得到 G、G1 和 G2。
- 去除G2中的红边，将G1中的每条红边改为指向G2中对应的顶点而不是G1中，将G中的每条红边指向G1中对应的顶点。
- 现在，每条有 2 个红色边的路径都在 G2 中结束，所有有 2 个红色边的路径都在 G2 中结束。类似地，所有具有 1 个红色边缘的路径最终都在 G1 中。使用 Dijkstra 算法找到从 G 中的 s 到 G、G1 和 G2 中所有顶点的最短路径。
- 对于G中的每个顶点，查看到G中相应顶点的路径，G1和G2，取最短的一个，并将其转换回原始图形。 （因为少于2条红边的路径也是可以接受的）