c++ - 如果边没有按照权重的排序顺序插入到双端队列中，0-1 BFS 是否会产生正确的答案？

Question

0-1 BFS算法的总体趋势是:如果遇到权重为0的边，则将节点推到双端队列的前面，如果边的权重为1，则将其推到双端队列的前面双端队列的后面。

如果我们随机推边，那么0-1 BFS能算出正确答案吗？如果在双端队列中输入的边未按其权重排序怎么办？

---

这是一般的0-1 BFS算法。如果我跳过最后的 if 和 else 部分并随机插入边缘，那么会发生什么？

对我来说，它应该可以，但是为什么这个算法是这样做的呢？

void bfs (int start)
{
    std::deque<int> Q; // double ended queue
    Q.push_back(start); 
    distance[start] = 0;       
    while(!Q.empty())
    {
        int v = Q.front();
        Q.pop_front(); 
        for(int i = 0 ; i < edges[v].size(); i++)
        {
            // if distance of neighbour of v from start node is greater than sum of 
            // distance of v from start node and edge weight between v and its 
            // neighbour (distance between v and its neighbour of v) ,then change it
            if(distance[edges[v][i].first] > distance[v] + edges[v][i].second) 
            {
                distance[edges[v][i].first] = distance[v] + edges[v][i].second;

                // if edge weight between v and its neighbour is 0 
                // then push it to front of
                // double ended queue else push it to back
                if(edges[v][i].second == 0)
                {
                    Q.push_front(edges[v][i].first);
                }
                else
                {
                    Q.push_back(edges[v][i].first);
                }
            }
        }  
    }
}

Answer 1

一切都是性能问题。虽然随机插入仍然可以找到最短路径，但您必须考虑更多路径(图形大小呈指数级)。所以基本上，结构化插入保证了线性时间复杂度。让我们从 0-1 BFS 保证这种复杂性的原因开始。

基本思想与Dijkstra算法相同。您访问按距离起始节点的距离排序的节点。这确保您不会发现会减少到目前观察到的节点的距离的边(这将需要您再次计算整个子图)。

在 0-1 BFS 中，您从起始节点开始，队列中的距离为:

d = [ 0 ]

然后你考虑所有的邻居。如果边缘权重为零，则将其推到前面，如果是一个，则推到后面。所以你得到一个这样的队列:

d = [ 0 0 0 1 1]

现在您获取第一个节点。它可能有零权重边的邻居和一权重边的邻居。所以你做同样的事情，最后得到一个这样的队列(新节点用 * 标记):

d = [ 0* 0* 0 0 1 1 1*]

因此，如您所见，节点仍按距离排序，这很重要。最终，你会到达这个状态:

d = [ 1 1 1 1 1 ]

从第一个节点经过零权重边产生的总路径长度为 1。经过单权重边产生两条路径。所以做0-1 BFS，你会得到:

d = [ 1* 1* 1 1 1 1 2* 2*]

等等... 总而言之，该过程需要确保您按照节点到起始节点的距离顺序访问节点。如果这样做，您将只考虑每条边两次(一次在向前方向，一次在向后方向)。这是因为当访问一个节点时，你知道你不能以更小的距离再次到达该节点。当您访问节点时，您只考虑从节点发出的边缘。因此，即使该节点被其邻居之一再次添加到队列中，您也不会访问它，因为生成的距离不会小于当前距离。这保证了O(E)的时间复杂度，其中E是边数。

那么，如果您不访问按距离起始节点的距离排序的节点，会发生什么情况？实际上，该算法仍然会找到最短路径。但是它会考虑更多的路径。因此，假设您访问了一个节点，并且该节点被其邻居之一再次放入队列中。这一次，我们不能保证最终的距离不会变小。因此，我们可能需要再次访问它并将它的所有邻居再次放入队列中。这同样适用于邻居，所以在最坏的情况下，这可能会传播到整个图形，最终你会一遍又一遍地访问节点。您最终会找到解决方案，因为您总是缩短距离。但所需时间远远超过智能 BFS。