在最多包含两条红边的图中寻找最短路径 [英] Find the shortest path in an graph containing at most two red edges

问题描述

问题是：

我知道我们应该将图形复制到G1和G2中，并可能使用Dijstra算法。我不确定我应该如何将G1和G2联系起来，这样我才能获得此问题的正确解决方案。

推荐答案

您几乎得到了答案：

1. 再复制两份图表，这样就有了G、G1和G2。
2. 删除G2中的红色边，将G1中的每条红色边更改为指向G2中的对应顶点，而不是G1，并将G中的每条红色边更改为指向G1中的相应顶点。
3. 现在，每条有两条红边的路径在G2中结束，所有有两条红边的路径在G2中结束。类似地，所有有1条红色边的路径都以G1结尾。使用Dijkstra算法找出从G中的s到G、G1和G2中的所有顶点的最短路径。
4. 对于G中的每个顶点，查看到G、G1和G2中相应顶点的路径，取最短的一个，并将其转换回原始图。(因为红边少于2条的路径也可以接受)

这篇关于在最多包含两条红边的图中寻找最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！