令 G=(V,E) 是一个无向图，s 和 t 是 V 中的两个顶点。图的每条边都被着色为红色或蓝色。我需要找到一种算法来找到 s 和 t 之间的路径，其中红色边缘的数量最少。
我想到了以下算法： A modified BFS algorithm
对于每个顶点，我们将使用一个名为“red level”的额外字段，它将指示从 s 到该顶点的路径上的最小红色边数。一旦我们发现了一个新的顶点，我们将更新它的红色级别字段。如果我们试图探索一个已经发现的顶点，如果这个顶点的红色级别大于当前的红色级别，那么我们从 BFS 树中删除这个顶点并将它作为我们的子节点的子节点插入现在正在探索，等等。期望的路径是在算法运行结束时连接 BFS 树中的 s 和 t 的路径。
我现在正试图证明这个算法是正确的，但收效甚微。我也不确定它是否真的正确。任何提示/想法？
我认为这是正确的：本质上，您正在使用Dijkstra 算法，红色边缘的权重非常大，蓝色边缘的权重非常小或为零。
不幸的是，该算法是不正确的。取下图： G = (V,E) ; V = {s, a, b, c, d, e, t} ; E = { (s,a), [s,b], [s,d], (a,b), [b,c], [d,e], (c,t), (e,t) } ;
（为方便起见，我将 ( , ) 标记为蓝色无向边，将 [ , ] 标记为红色无向边）
假设算法选择在“a”之前探索“b”。当我们完成 's' 后，我们将有红色级别 0 的 'a'，红色级别 1 的 'b' 和 'd'。在从 'd' 探索时，我们将有 'e'红色级别 2。现在我们从 'b' 开始探索：'s' 和 'a' 保持不变，但 'c' 得到红色级别 2。接下来我们探索 'a'（根据 BFS！），它将“b”的父级更改为“a”，将“b”的红色级别更改为 0。请注意，在这一点上 - 从“s”到“c”的路径是正确的，但红色级别'c' 不是 - 它应该是 1 而不是 2。现在，我们继续前进，我们从 'e' 开始（我们已经完成了 's' 及其直系子 'a'、'b' 和'd'）：我们发现't'与边缘（e，t），所以't'得到红色级别2。边缘（e，d）没有改变。现在我们进入了很酷的部分——从“c”开始探索：边 (c,b) 没有任何变化，但是边 (c,t) 呢？'t' 已经被发现（来自 'e'），因此根据您的算法，我们仅在红色级别存在差异时才更改某些内容。但是没有，因为“c”的红色级别是 2（不正确！）。所以't'的父级仍然是'e'，并且从's'的路径包含2个红色边缘，而从's'到't'的路径只包含1个红色边缘：s -> a -> b -> c -> t 边 (c,b) 什么都没有改变，但是边 (c,t) 呢？'t' 已经被发现（来自 'e'），因此根据您的算法，我们仅在红色级别存在差异时才更改某些内容。但是没有，因为“c”的红色级别是 2（不正确！）。所以't'的父级仍然是'e'，并且从's'的路径包含2个红色边缘，而从's'到't'的路径只包含1个红色边缘：s -> a -> b -> c -> t 边 (c,b) 什么都没有改变，但是边 (c,t) 呢？'t' 已经被发现（来自 'e'），因此根据您的算法，我们仅在红色级别存在差异时才更改某些内容。但是没有，因为“c”的红色级别是 2（不正确！）。所以't'的父级仍然是'e'，并且从's'的路径包含2个红色边缘，而从's'到't'的路径只包含1个红色边缘：s -> a -> b -> c -> t