在一个有色图中寻找最短路径。

Question

我试图解决的问题是：

给定一张由红色或蓝色着色的边构成的图：

a) 给出一个算法，产生一条经过最少红色边的、连接起点(s)和终点(t)的路径。

b) 给出一个算法，找到一条从s到t的路径，并且该路径上的红边最少，而蓝边最少（当选择重复数量的情况下）。

迄今为止： 对于a)，我可以使用修改后的BFS算法。当查看节点v时，首先将所有通过蓝色边与v相连的节点放入队列中，然后将其余节点添加到队列的末尾。因此，算法第一次遇到t时，即为所求路径。

如何证明这个算法的正确性？它似乎非常贪心。如何扩展以回答b)?

感谢您的时间。

- user3392518

---

如果从s出发的“蓝色”路径在到达t的节点之前有两条“红色”路径，而从s出发的第一条“红色”路径只有通过“蓝色”节点路径才能到达t，那么你的策略会出现反例。 - ErstwhileIII

你考虑过给图加权吗？对于A，你可以将蓝色边的权重赋为0，将红色边的权重赋为1，然后找到成本最小的路径。然后对于B，只需反转权重即可。 - Joel

@Joel：你对 b) 的建议不可行，因为我们仍然主要想要最小化红边。蓝边只是用作决定胜负的关键因素。 - Niklas B.

@ErstwhileIII：OP的算法仍然会找到正确的路径。你可以在纸上验证一下。 - Niklas B.

@NiklasB。啊，你说得完全正确，我误读了B中被询问的内容。 - Joel

Answer 1

你的算法需要记住两个重要细节：

1. 在你的情况下，节点可以被添加到队列多次。但是你只能探索一次。你可以通过为每个节点维护一个布尔标志来强制执行该操作，以告诉你是否已经探索过一个节点。

2. 你只能在将t从队列中取出时停止算法，而不能在将t放入队列时就停止。

如果你按照这种方式进行操作(你的问题没有表明你不这样做)，那么你的算法确实是正确的。

如果你将红边的边权赋值为1，并将蓝边的边权赋值为0，则问题转化为在转换后的图中找到最短路径。让我们将Dijkstra应用于这个问题。我将展示你的算法实际上实现了Dijkstra算法，从而证明了它的正确性。

我们可以证明，在优先队列中，我们只有两个不同距离的节点：如果m是优先队列中节点的最小距离，则我们不能在队列中有距离为m+2的节点，因为这意味着我们必须已经探索了一个距离为m+1的节点，这是不可能的，因为我们按递增距离的顺序探索节点。

你修改的BFS实际上使用双端队列作为2值优先队列实现了Dijkstra算法：如果Q是你的队列，则有一个索引i，使得Q[1..i]仅包含距离为m的节点，Q[i+1..]仅包含距离为m+1的节点。

你可以通过维护一个4值优先队列来扩展这个概念，例如实现为两个双端队列。一个队列将保存距离为m的红边节点，另一个队列将保存距离为m+1的红边节点。两个队列都按递增蓝边数量排序(每个队列中也只有两个不同的距离值)。

- Niklas B.

Answer 2

如果您将与蓝色边相邻的节点放在队列前面而不是队列末尾，算法就是正确的，正如评论中所讨论的。

对于问题（B），只需丢弃不在原始最短路径（使用最小红边）中的边。如果边u-v在最短路径中，则很容易找到。如果distance[source][u]+cost[u][v]+distance[v][destination]=distance[source][destination]，则u-v在最短路径中。在丢弃额外的边之后，其余的任务就很容易了。

- Shafaet

---

OP的算法实际上是正确的。它找到了右边的最短路径。 - Niklas B.

不会的。他永远不会到达 b，因为它是在队列末尾添加的（在 c 之后），而 d 是在探索 c 之后添加到队列前面的。 - Niklas B.

也许我需要存储类似“当前最短路径”的内容，并在每次到达t时更新它，以使算法正确？感谢您的回答。 - user3392518

你能在BFS中在队列前面添加一个节点吗？我认为不行，因为你没有按层遍历。我想他的意思是先处理蓝色边，然后再处理红色边。 - Shafaet

@Shafaet：是的，你可以，顺序无关紧要。引用问题中的一句话：“将所有通过蓝边连接到v的顶点放在队列的前面，然后将其余部分添加到队列的末尾”，这是有效的并产生了正确的算法。 - Niklas B.