Roy*_*Roy 2 language-agnostic algorithm graph-theory
设G =(V,E)是无向图,s和t是V中的两个顶点.图的每个边都用红色或蓝色着色.我需要找到一种算法,找到s和t之间的路径,其中红色边缘的数量最少.
我想到了以下算法:一种改进的BFS算法
对于每个顶点,我们将使用一个名为"红色级别"的额外字段,它将指示从s到此顶点的路径上的最小红边数.一旦我们发现了一个新的顶点,我们将更新其红色级别字段.如果我们正在尝试探索已经发现的顶点,如果此顶点的红色级别大于当前红色级别,那么我们将从BFS树中删除此顶点并将其作为子节点的子节点插入其中正在探索,等等.所需的路径是在算法运行结束时连接BFS树中的s和t的路径.
我现在正在尝试证明这个算法是正确的,但收效甚微.我也不确定它是否确实是正确的.任何提示/想法？