Input: 我们有一个有向图G =（V，E），每个边都有一个权重和一个颜色{红色，绿色} . 我们还给出了一个起始节点 .
Problem/Algorithm: 我们能找到G的所有u边缘，最短路径s-u最多为k个红色边缘吗？
First approach: 我们为每个节点保存最短路径，其中0,1 ... k为红色边缘 . 我们修改了Dijkstra的算法，并根据我们正在研究的边缘的颜色，我们分别更新距离 . 这种方法由于其复杂性而失败 .
Second approach: 我们制作G图的k个副本（G1，G2 ... Gk 1） . 为了利用k红色边缘约束，当我们用Dijkstra搜索最短路径时，每当我们在Gi中使用红色边缘{ui，vi}时，我们将ui与Gi 1中的vi 1连接起来 . 因为Gk 1没有t有任何红色边缘，我们只能达到最多k个边缘的Gk 1 . 但它失败了 . 例如，如果向X节点发现2个红色边缘最短路径，则k = 2，则不会考虑具有较少红色边缘的较重路径，这可能导致未发现的节点 . （如果我有足够的声誉，我可以发布一个图像作为例子） .
有任何想法吗 ？
1 回答
我认为你的方法实际上是等价的，只要对于方法＃1，你只记录每个节点使用的每个红色边缘的最短距离 - 你不需要在普通的最短路径问题上为普通Dijkstra记录它 . ）
这种方法也很健全 . 特别是，你认为方法＃2有缺陷的原因本身是错误的：对于原始图中的任何节点X，新图中没有单个对应的节点X;相反，对于每个使用的红色边数，都有单独的顶点 . 所以你考虑的两个路径实际上并不是同一个节点：一个是（X，使用了2个红色边缘），一个是例如（X，使用1个红边） . 然后你可以使用单个Dijkstra运行来计算每个顶点的所有k 1个副本的最短路径（即到每个0 <= i <= k的顶点（v，i红色边缘）和V中的每个v（G） ）），并返回最低 . （我在这里假设当你写了"Can we find for all u edges of G, the shortest paths s-u"时，你的意思是“对于G的所有节点u，最短的路径s-u” . ）
最后，您需要确保对于G中的任何红色边缘{u，v}，您删除所有Gi的相应边{ui，vi}（以及添加边{ui，vi 1}） . 你可能打算这样做，但你并没有明确这一点 .