输入:我们有一个有向图 G=(V,E)，每条边都有一个权重和颜色 {red,green}。我们还给出了一个起始节点 s。
问题/算法:我们能否找到 G 的所有 u 条边，最多有 k 条红色边的最短路径 s-u ？< br/>
第一种方法:我们为每个节点保存具有 0,1...k 条红边的最短路径。我们修改 Dijkstra 算法，并根据我们正在研究的边缘的颜色，分别更新距离。这种方法由于其复杂性而失败。
第二种方法:我们制作 G 图的 k 个副本 (G1,G2 ...Gk+1)。为了利用 k 个红边约束，当我们用 Dijkstra 搜索最短路径时，每次我们在 Gi 中“遇到”红边 {ui,vi} 时，我们就将 ui 与 Gi+1 中的 vi+1 连接起来。因为Gk+1没有任何红边，所以我们最多只能用k条边到达Gk+1。但是它失败了。例如，当 k=2 时，如果找到到 X 节点的 2 个红边最短路径，则不会考虑具有较少红边的较重路径，这可能导致未发现的节点。 (如果我有足够的声誉，我可以发布图片作为示例)。
有什么想法吗？
最佳答案
我认为您的方法实际上是等效的，前提是对于方法＃1，您仅记录所使用的每个红色边数到每个节点的最短距离 - 您不需要记录整个路径(就像在普通最短路径问题上不需要记录普通 Dijkstra 一样)
这种方法也是合理的。特别是，您关于方法 #2 错误的推理本身就是错误的:对于原始图中的任何节点 X，新图中没有单个对应的节点 X；相反，每个使用的红色边数都有单独的顶点。因此，您正在考虑的“到 X”的两条路径实际上并不是到同一个节点:一条是到(X，使用 2 个红色边缘)，另一条是到例如(X，使用 1 个红边)。然后，您可以使用单个 Dijkstra 运行来计算到每个顶点的所有 k+1 个副本(即到每个 0 <= i <= k 和 V 中的每个 v 的顶点(v，i 使用的红色边)的最短路径( G))，并返回最低的。 (我在这里假设，当你写“我们能否找到 G 的所有 u 边，最短路径 s-u”时，你的意思是“对于 G 的所有节点 u，最短路径 s-u”。 )
最后，您需要确保对于 G 中的任何红色边 {u, v}，删除所有 Gi 的相应边 {ui, vi}(并添加边 {ui, vi+1 })。您可能有意这样做，但您没有明确表示。
关于algorithm - 具有 2 个约束(权重和颜色)的最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28241901/