Блог

Общая тенденция алгоритмов 0-1 BFS такова: если встречается ребро с весом = 0, то узел перемещается в начало deque, а если вес ребра = 1, то он будет перемещен в конец deque.

Если мы случайным образом сдвинем ребра, то сможет ли 0-1 BFS вычислить правильный ответ? Что, если ребра введены в deque не в отсортированном порядке их весов?

Это общий алгоритм 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);
                }
            }
        }  
    }
}
  

Это все вопрос производительности. В то время как случайная вставка все еще находит кратчайший путь, вам нужно рассмотреть намного больше путей (экспоненциально в размере графика). Таким образом, в принципе, структурированная вставка гарантирует линейную временную сложность. Давайте начнем с того, почему 0-1 BFS гарантирует такую сложность.

Основная идея та же, что и в алгоритме Дейкстры. Вы посещаете узлы, упорядоченные по их расстоянию от начального узла. Это гарантирует, что вы не обнаружите ребро, которое уменьшило бы расстояние до наблюдаемого до сих пор узла (что потребовало бы от вас повторного вычисления всего подграфа).

В 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 — количество ребер.

Итак, что бы произошло, если бы вы не посещали узлы, упорядоченные по их расстоянию от начального узла? На самом деле, алгоритм все равно нашел бы кратчайший путь. Но при этом будет учитываться намного больше путей. Итак, предположим, что вы посетили узел, и этот узел снова помещен в очередь одним из его соседей. На этот раз мы не можем гарантировать, что результирующее расстояние не будет меньше. Таким образом, нам, возможно, потребуется посетить его снова и снова поместить всех его соседей в очередь. И то же самое относится к соседям, так что в худшем случае это может распространиться по всему графику, и вы в конечном итоге будете посещать узлы снова и снова. В конечном итоге вы найдете решение, потому что вы всегда уменьшаете расстояние. Но требуется гораздо больше времени, чем для smart BFS.