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 ]

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

d = [ 0 0 0 1 1]

现在您获取第一个节点。它可能具有零权重边的邻居和一权重边的邻居。因此，您执行相同的操作，最终得到一个像这样的队列(新节点标有 *):

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

正如您所见，节点仍然按距离排序，这是至关重要的。最终，你会达到这样的状态:

d = [ 1 1 1 1 1 ]

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

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

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

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