Изменения

Пусть задан невзвешенный ориентированный граф <tex> G = (V, E) </tex>, в котором выделена исходная вершина <tex>s</tex>. Для алгоритма нам потребуются [[Очередь|очередь]]Требуется найти длину кратчайшего пути (если таковой имеется) от одной заданной вершины до другой. Частным случаем указанного графа является невзвешенный неориентированный граф, которая сначала содержит только <tex> s </tex>, и множество посещенных вершин <tex> X </tex>, которое изначально тоже содержит только <tex> s </tex>т.е. На каждом шаге алгоритм вынимает из начала очереди вершинуграф, рассматривает все исходящие из нее в котором для каждого ребра и добавляет все связанные с ней непосещенные найдется обратное, соединяющее те же вершины в <tex> X </tex> и в конец очереди. Если очередь пуста, то алгоритм завершает работудругом направлении.

Для алгоритма нам потребуются [[Очередь|очередь]], которая сначала содержит только <tex> s </tex>, и множество посещенных вершин <tex> X </tex>, которое изначально тоже содержит только <tex> s </tex>. На каждом шаге алгоритм вынимает из начала очереди вершину, рассматривает все исходящие из нее ребра и добавляет все связанные с ней непосещенные вершины в <tex> X </tex> и в конец очереди. Если очередь пуста, то алгоритм завершает работу. Поиск в ширину также может построить [[Дерево, эквивалентные определения|дерево ]] поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>.

Оценим время работы для входного графа <tex>G = (V, E)</tex>, где <tex> E </tex> представлены списком смежности. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> \mathrm{deg\ }(v ) </tex> ребер, инцидентных ей. Так как <tex> \sum\limits_{v \in V} \mathrm{deg\ }(v ) = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </tex>.

'''База''': изначально очередь содержит только одну вершину <tex> s </tex> с расстоянием <tex> 0</tex>, утверждение верно.

'''Переход''': пусть после <tex> l </tex>-ого шага алгоритма очередь содержит <tex> p </tex> вершин с расстоянием <tex> k </tex> и <tex> q </tex> вершин с расстоянием <tex> k + 1 </tex>. Тогда на <tex> l+1 </tex>-ом шаге мы извлечем из очереди одну вершину и добавим в нее все непосещенные(<tex> r </tex> вершин), связанные с ней; расстояние до них, очевидно, будет равно <tex> k + 1 </tex>. У нас останется <tex> p - 1 </tex> (возможно, <tex> 0</tex>) вершин с расстоянием <tex> k </tex> и <tex> q + r </tex> вершин с расстоянием <tex> k + 1</tex>, что соответствует нашему инварианту.

Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами .<ul> <li><tex> \mathtt{source } </tex> — исходная вершина</li> <li><tex> \mathtt{destination} </tex> — конечная вершина</li> <li><tex> \mathtt{G} </tex> — граф, состоящий из списка вершин <tex> \mathtt{V} </tex> и destinationсписка смежности <tex> \mathtt{E} </tex>. Вершины нумеруются целыми числами. E - список ребер, </li> <li><tex> \mathtt{Q - } </tex> — очередь. Множество </li> <li>В поле <tex> X \mathtt{d[u]} </tex> не хранится, вместо него используются расстояния в дереве обхода в ширину. Заметим, что расстояние от вершины <tex> \mathtt{source } </tex> до вершины <tex> \mathtt{u, хранится в поле d[u]} </tex>.</li></ul>

'''int''' '''BFS'''(E: '''list'''<'''int'''V, '''int'''E>, source: '''int''', destination: '''int''') d = int[|V|]

q u = Q.pop() '''for''' <q, v> vu '''in''' E

Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение <tex> \mathtt{d[destination]} </tex>. == Примеры задач Вариации алгоритма ==

Пусть в графе разрешены ребра веса <tex> 0 </tex> и <tex> 1</tex>, необходимо найти кратчайший путь между двумя вершинами. Для решения данной задачи модифицируем приведенный выше алгоритм следующим образом: вместо очереди будем использовать [[Персистентный_дек|декdeque]](steque), а вместо добавления вершины в конец будем добавлять вершину в начало, если рассматриваемое ее ребро имеет вес <tex> 0</tex>, а иначе в конец. Соответственно релаксируем расстояние до вершины. Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант [[#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется. Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного BFS.

Пусть в графе разрешены ребра целочисленного веса из отрезка <tex>1..k</tex>, необходимо найти кратчайший путь между двумя вершинами. Представим ребро <tex>uv</tex> веса <tex>m</tex> как последовательность ребер <tex>uu_1u_2..u_{m - 1}v</tex> (где <tex>u_1..u_{m - 1}</tex> - новые вершины). Применим данную операцию ко всем ребрам графа <tex>G(V, E)</tex>. Получим граф, состоящий (в худшем случае) из <tex>k|E|</tex> ребер и <tex>|V| + (k - 1)|E|</tex> вершин. Для нахождения кратчайшего пути следует запустить BFS на новом графе. Асимптотикой данного алгоритма является <tex> O(|V| + (2k - 1)k|E|) </tex>.