Обход в ширину — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Общая идея)
м (rollbackEdits.php mass rollback)
 
(не показано 56 промежуточных версий 16 участников)
Строка 1: Строка 1:
'''Обход в ширину''' ('''Поиск в ширину, BFS''', Breadth-first search) — один из простейших алгоритмов обхода графа, являющийся основой для многих важных алгоритмов для работы с графами. Например, алгоритм [[Алгоритм Прима|Прима]] поиска минимального остовного дерева или алгоритм [[Алгоритм Дейкстры|Дейкстры]] поиска кратчайшего пути из одной вершины используют идеи, сходные идеям, используемым при поиске в ширину.
+
'''Обход в ширину''' (Поиск в ширину, англ. ''BFS'', ''Breadth-first search'') — один из простейших алгоритмов обхода [[Основные определения теории графов|графа]], являющийся основой для многих важных алгоритмов для работы с графами.
  
==Алгоритм==
+
== Описание алгоритма ==
 +
[[Image: Graph-BFS.gif|thumb|240px|Алгоритм BFS<br>
 +
<font color=#3c9eff>посещенные</font> вершины<br>]]
  
===Общая идея===
 
Пусть задан граф <tex>G = (V, E)</tex> и выделена исходная вершина <tex>s</tex>. Алгоритм поиска в ширину систематически обходит все ребра <tex>G</tex> для "открытия" всех вершин, достижимых из <tex>s</tex>, вычисляя при этом расстояние (минимальное количество ребер) от <tex>s</tex> до каждой достижимой из <tex>s</tex> вершины. Кроме того, в процессе обхода строится "дерево поиска в ширину" с корнем <tex>s</tex>, содержащее все достижимые вершины. Для каждой достижимой их <tex>s</tex> вершины <tex>v</tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex>s</tex> до <tex>v</tex> в <tex>G</tex>.
 
  
Для отслеживания работы алгоритма поиск в ширину раскрашивает вершины графа в белый, серый и черный цвета. Изначально все вершины белые, и позже они могут стать серыми, а затем черными. Когда вершина '''открывается''' в процессе поиска, она окрашивается. Таким образом, серые и черные вершины — это вершины, которые уже были открыты, но алгоритм поиска в ширину по-разному работает с ними, чтобы обеспечить объявленный порядок обхода. Если <tex>(u, v) \in E</tex> и вершина <tex>u</tex> черного цвета, то вершина <tex>v</tex> либо серая, либо черная, т.е. все вершины, смежные с ней уже открыты. Серые вершины могут иметь белых соседей, представляя собой границу между открытыми и неоткрытыми вершинами.
+
Пусть задан невзвешенный ориентированный граф <tex> G = (V, E) </tex>, в котором выделена исходная вершина <tex>s</tex>. Требуется найти длину кратчайшего пути (если таковой имеется) от одной заданной вершины до другой. Частным случаем указанного графа является невзвешенный неориентированный граф, т.е. граф, в котором для каждого ребра найдется обратное, соединяющее те же вершины в другом направлении.
  
Поиск в ширину стоит дерево поиска в ширину, которое изначально состоит из одного корня, которым является исходная вершина <tex>s</tex>. Если в процессе сканирования списка смежности уже открытое вершины <tex>u</tex> открывается белая вершина <tex>v</tex>, то вершина <tex>v</tex> и ребро <tex>(u, v)</tex> добавляются в дерево. При этом <tex>u</tex> является '''предшественником''' (predecessor), или '''родителем''' (parent), <tex>v</tex> в дереве поиска в ширину. Поскольку вершина может быть открыта не более одного раза, она имеет не более одного родителя.
+
Для алгоритма нам потребуются [[Очередь|очередь]] и множество посещенных вершин <tex> was </tex>, которые изначально содержат одну вершину <tex> s </tex>. На каждом шагу алгоритм берет из начала очереди вершину <tex> v </tex> и добавляет все непосещенные смежные с <tex> v </tex> вершины в <tex> was </tex> и в конец очереди. Если очередь пуста, то алгоритм завершает работу.
  
=== Реализация===
+
== Анализ времени работы ==
Приведенная ниже процедура поиска в ширину '''BFS''' предполагает, что входной граф <tex>G = (V, E)</tex> представлен при помощи списков смежности. Кроме того, поддерживаются дополнительные структуры данных в каждой вершине графа. Цвет каждой вершины <tex>u \in V</tex> хранится в переменной <tex>color[u]</tex>, а предшественник — в переменной <tex>p[u]</tex>. Если прежшественника у <tex>u</tex> нет, то <tex>p[u] =</tex> NIL. Расстояние от <tex>s</tex> до вершины <tex>u</tex>, вычисляемое алгоритмом, хранится в поле <tex>d[u]</tex>. Алгоритм использует очередь <tex>Q</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>.
'''BFS'''(<tex>G</tex>, <tex>s</tex>)
 
  1  '''for''' (для) каждой вершины <tex>u \in V[G] - s</tex>
 
  2    '''do'''  <tex>color[u] \leftarrow</tex> WHITE
 
  3      <tex>d[u] \leftarrow \mathcal {1}</tex>
 
  4      <tex>p[u] \leftarrow</tex> NIL
 
  5  <tex>color[s] \leftarrow</tex> GRAY
 
  6  <tex>d[s] \leftarrow</tex> 0
 
  7  <tex>p[s] \leftarrow</tex> NIL
 
  8  <tex>Q \leftarrow</tex> Ø
 
  9  ENQUEUE(<tex>Q</tex>, <tex>s</tex>)
 
  10 '''while''' <tex>Q \ne </tex>Ø
 
  11  '''do''' <tex>u \leftarrow</tex> DEQUEUE(<tex>Q</tex>)
 
  12    '''for''' (для) каждой <tex>м \in Adj[u]</tex>
 
  13      '''do''' '''if''' <tex>color[u] =</tex> WHITE
 
  14        '''then''' <tex>color[v] \leftarrow</tex> GRAY
 
  15              <tex>d[v] \leftarrow d[u] + 1</tex>
 
  16              <tex>p[v] \leftarrow u</tex>
 
  17              ENQUEUE(<tex>Q</tex>, <tex>v</tex>)
 
  18    <tex>color[u] \leftarrow</tex>BLACK
 
  
== Анализ ==
+
== Корректность ==
Оценим время работы для входного графа <tex>G = (V, E)</tex>. После инициализации ни одна вершина не окрашивается в белый цвет, поэтому проверка в строке 13 гарантирует, что каждая вершина вносится в очередь не более одного раза, а следовательно, и удаляется из очереди она не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex>O(1)</tex> времени, так что общее время операций с очередью составляет <tex>O(V)</tex>. Поскольку каждый список смежности сканируется только при удалении соответствующей вершины из очереди, каждый список сканируется не более одного раза. Так как сумма длин всех списков смежности равна <tex> \Theta (E) </tex>, общее время, необходимое для сканирования списков, равно <tex>O(E)</tex>. Накладные расходы на инициализацию равны <tex>O(V)</tex>, так что общее время работы процедуры '''BFS''' составляет <tex>O(V + E)</tex>. Таким образом, время работы поиска в ширину линейно зависит от размера представления графа <tex>G</tex> с использованием списков смежности.
 
  
== Литература ==
+
{{Утверждение
*Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
+
|statement=
 +
В очереди поиска в ширину расстояние вершин до <tex>s</tex> монотонно неубывает.
 +
|proof=
 +
Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.
 +
 
 +
Введем дополнительный инвариант: у любых двух вершин из очереди, расстояние до <tex> s </tex> отличается не более чем на <tex> 1 </tex>. 
 +
 
 +
'''База''': изначально очередь содержит только одну вершину <tex> s </tex>.
 +
 
 +
'''Переход''': пусть после <tex> i-й </tex> итерации в очереди <tex> a + 1 </tex> вершин с расстоянием <tex> x </tex> и <tex> b </tex> вершин с расстоянием <tex> x + 1 </tex>.
 +
 
 +
Рассмотрим <tex> i-ю </tex> итерацию. Из очереди достаем вершину <tex> v </tex>, с расстоянием <tex> x </tex>. Пусть у <tex>v</tex> есть <tex>r  </tex> непосещенных смежных вершин. Тогда, после их добавления, в очереди находится <tex> a </tex> вершин с расстоянием <tex> x </tex> и, после них, <tex> b + r </tex> вершин с расстоянием <tex> x + 1 </tex>.
 +
 
 +
Оба инварианта сохранились, <tex>  \Rightarrow </tex> после любого шага алгоритма элементы в очереди неубывают.
 +
}}
 +
 
 +
{{Теорема
 +
|statement=
 +
Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин.
 +
|proof=
 +
Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от <tex> s </tex> найдены некорректно, ту, настоящее расстояние до которой минимально. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в кратчайшем пути до <tex> u </tex> — вершина <tex> w </tex>.
 +
 
 +
Так как <tex> w </tex> — предок <tex> u </tex> в кратчайшем пути, то <tex> \rho(s, u) = \rho(s, w) + 1 > \rho(s, w) </tex>, и расстояние до <tex> w </tex> найдено верно, <tex> \rho(s, w) = d[w] </tex>. Значит, <tex> \rho(s, u) = d[w] + 1 </tex>.
 +
 
 +
Так как <tex> v </tex> — предок <tex> u </tex> в дереве обхода в ширину, то <tex> d[u] = d[v] + 1 </tex>.
 +
 
 +
Расстояние до <tex> u </tex> найдено некорректно, поэтому <tex> \rho(s, u) < d[u] </tex>. Подставляя сюда два последних равенства, получаем <tex> d[w] + 1 < d[v] + 1 </tex>, то есть, <tex> d[w] < d[v] </tex>. Из ранее доказанной леммы следует, что в этом случае вершина <tex> w </tex> попала в очередь и была обработана раньше, чем <tex> v </tex>. Но она соединена с <tex> u </tex>, значит, <tex> v </tex> не может быть предком <tex> u </tex> в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.
 +
}}
 +
 
 +
== Дерево обхода в ширину ==
 +
 
 +
Поиск в ширину также может построить [[Дерево, эквивалентные определения|дерево]] поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>.
 +
 
 +
== Реализация ==
 +
 
 +
Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.
 +
*<tex> \mathtt{source} </tex> — исходная вершина
 +
*<tex> \mathtt{destination} </tex> — конечная вершина
 +
*<tex> \mathtt{G} </tex> — граф, состоящий из списка вершин <tex> \mathtt{V} </tex> и списка смежности <tex> \mathtt{E} </tex>. Вершины нумеруются целыми числами.
 +
*<tex> \mathtt{Q} </tex> — очередь.
 +
*В поле <tex> \mathtt{d[u]} </tex> хранится расстояние от <tex> \mathtt{source} </tex> до <tex> \mathtt{u} </tex>.
 +
 
 +
'''int''' '''BFS'''(G: (V, E), source: '''int''', destination: '''int'''):
 +
    d = '''int'''[|V|]
 +
    '''fill'''(d, <tex> \infty </tex>)
 +
    d[source] = 0
 +
    Q = <tex> \varnothing </tex>
 +
    Q.push(source)
 +
    '''while''' Q <tex> \ne \varnothing </tex>
 +
        u = Q.pop()
 +
        '''for''' v: (u, v) '''in''' E
 +
            '''if''' d[v] == <tex> \infty </tex>
 +
                d[v] = d[u] + 1
 +
                Q.push(v)
 +
    '''return''' d[destination]
 +
 
 +
Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение <tex> \mathtt{d[destination]} </tex>.
 +
Еще одна оптимизация может быть проведена при помощи метода [[Meet-in-the-middle#Задача о нахождении кратчайшего расстояния между двумя вершинами в графе|meet-in-the-middle]].
 +
 
 +
== Вариации алгоритма ==
 +
=== 0-1 BFS ===
 +
Пусть в графе разрешены ребра веса <tex> 0 </tex> и <tex> 1 </tex>, необходимо найти кратчайший путь между двумя вершинами. Для решения данной задачи модифицируем приведенный выше алгоритм следующим образом:
 +
 
 +
Вместо очереди будем использовать [[Персистентный_дек|дек]] (или можно даже steque). Если рассматриваемое ее ребро имеет вес <tex> 0 </tex>, то будем добавлять вершину в начало, а иначе в конец. После этого добавления, дополнительный введенный инвариант в доказательстве [[#Корректность | расположения элементов в деке в порядке неубывания]] продолжает выполняться, поэтому порядок в деке сохраняется. И, соответственно, релаксируем расстояние до всех смежных вершин и, при успешной релаксации, добавляем их в дек.
 +
 
 +
Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант [[#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется. Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного BFS.
 +
 
 +
=== 1-k BFS ===
 +
Пусть в графе разрешены ребра целочисленного веса из отрезка <tex>1 \ldots k</tex>, необходимо найти кратчайший путь между двумя вершинами. Представим ребро <tex>uv</tex> веса <tex>m</tex> как последовательность ребер <tex>uu_1u_2 \ldots u_{m - 1}v</tex> (где <tex>u_1 \ldots u_{m - 1}</tex> — новые вершины). Применим данную операцию ко всем ребрам графа <tex> G </tex>. Получим граф, состоящий (в худшем случае) из <tex>k|E|</tex> ребер и <tex>|V| + (k - 1)|E|</tex> вершин. Для нахождения кратчайшего пути следует запустить BFS на новом графе. Данный алгоритм будет иметь асимптотику <tex> O(|V| + k|E|) </tex>.
 +
 
 +
== См. также ==
 +
* [[Обход в глубину, цвета вершин]]
 +
* [[Алгоритм Дейкстры]]
 +
* [[Теория графов]]
 +
 
 +
== Источники информации ==
 +
 
 +
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
 +
* [http://e-maxx.ru/algo/bfs MAXimal :: algo :: Поиск в ширину]
 +
* [[wikipedia:en:Breadth-first_search| Wikipedia {{---}} Breadth-first search]]
 +
* [[wikipedia:ru:Поиск_в_ширину| Wikipedia {{---}} Поиск в ширину]]
 +
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bfs-2002 Визуализатор алгоритма]
 +
 
 +
 
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Кратчайшие пути в графах]]

Текущая версия на 19:35, 4 сентября 2022

Обход в ширину (Поиск в ширину, англ. BFS, Breadth-first search) — один из простейших алгоритмов обхода графа, являющийся основой для многих важных алгоритмов для работы с графами.

Описание алгоритма

Алгоритм BFS
посещенные вершины


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

Для алгоритма нам потребуются очередь и множество посещенных вершин [math] was [/math], которые изначально содержат одну вершину [math] s [/math]. На каждом шагу алгоритм берет из начала очереди вершину [math] v [/math] и добавляет все непосещенные смежные с [math] v [/math] вершины в [math] was [/math] и в конец очереди. Если очередь пуста, то алгоритм завершает работу.

Анализ времени работы

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

Корректность

Утверждение:
В очереди поиска в ширину расстояние вершин до [math]s[/math] монотонно неубывает.
[math]\triangleright[/math]

Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.

Введем дополнительный инвариант: у любых двух вершин из очереди, расстояние до [math] s [/math] отличается не более чем на [math] 1 [/math].

База: изначально очередь содержит только одну вершину [math] s [/math].

Переход: пусть после [math] i-й [/math] итерации в очереди [math] a + 1 [/math] вершин с расстоянием [math] x [/math] и [math] b [/math] вершин с расстоянием [math] x + 1 [/math].

Рассмотрим [math] i-ю [/math] итерацию. Из очереди достаем вершину [math] v [/math], с расстоянием [math] x [/math]. Пусть у [math]v[/math] есть [math]r [/math] непосещенных смежных вершин. Тогда, после их добавления, в очереди находится [math] a [/math] вершин с расстоянием [math] x [/math] и, после них, [math] b + r [/math] вершин с расстоянием [math] x + 1 [/math].

Оба инварианта сохранились, [math] \Rightarrow [/math] после любого шага алгоритма элементы в очереди неубывают.
[math]\triangleleft[/math]
Теорема:
Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин.
Доказательство:
[math]\triangleright[/math]

Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от [math] s [/math] найдены некорректно, ту, настоящее расстояние до которой минимально. Пусть это вершина [math] u [/math], и она имеет своим предком в дереве обхода в ширину [math] v [/math], а предок в кратчайшем пути до [math] u [/math] — вершина [math] w [/math].

Так как [math] w [/math] — предок [math] u [/math] в кратчайшем пути, то [math] \rho(s, u) = \rho(s, w) + 1 \gt \rho(s, w) [/math], и расстояние до [math] w [/math] найдено верно, [math] \rho(s, w) = d[w] [/math]. Значит, [math] \rho(s, u) = d[w] + 1 [/math].

Так как [math] v [/math] — предок [math] u [/math] в дереве обхода в ширину, то [math] d[u] = d[v] + 1 [/math].

Расстояние до [math] u [/math] найдено некорректно, поэтому [math] \rho(s, u) \lt d[u] [/math]. Подставляя сюда два последних равенства, получаем [math] d[w] + 1 \lt d[v] + 1 [/math], то есть, [math] d[w] \lt d[v] [/math]. Из ранее доказанной леммы следует, что в этом случае вершина [math] w [/math] попала в очередь и была обработана раньше, чем [math] v [/math]. Но она соединена с [math] u [/math], значит, [math] v [/math] не может быть предком [math] u [/math] в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.
[math]\triangleleft[/math]

Дерево обхода в ширину

Поиск в ширину также может построить дерево поиска в ширину. Изначально оно состоит из одного корня [math] s [/math]. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из [math] s [/math] вершины [math] t [/math] путь в дереве поиска в ширину соответствует кратчайшему пути от [math] s [/math] до [math] t [/math] в [math] G [/math].

Реализация

Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.

  • [math] \mathtt{source} [/math] — исходная вершина
  • [math] \mathtt{destination} [/math] — конечная вершина
  • [math] \mathtt{G} [/math] — граф, состоящий из списка вершин [math] \mathtt{V} [/math] и списка смежности [math] \mathtt{E} [/math]. Вершины нумеруются целыми числами.
  • [math] \mathtt{Q} [/math] — очередь.
  • В поле [math] \mathtt{d[u]} [/math] хранится расстояние от [math] \mathtt{source} [/math] до [math] \mathtt{u} [/math].
int BFS(G: (V, E), source: int, destination: int):
    d = int[|V|]
    fill(d, [math] \infty [/math])
    d[source] = 0
    Q = [math] \varnothing [/math]
    Q.push(source)
    while Q [math] \ne \varnothing [/math] 
        u = Q.pop()
        for v: (u, v) in E
            if d[v] == [math] \infty [/math]
                d[v] = d[u] + 1
                Q.push(v)
    return d[destination]

Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение [math] \mathtt{d[destination]} [/math]. Еще одна оптимизация может быть проведена при помощи метода meet-in-the-middle.

Вариации алгоритма

0-1 BFS

Пусть в графе разрешены ребра веса [math] 0 [/math] и [math] 1 [/math], необходимо найти кратчайший путь между двумя вершинами. Для решения данной задачи модифицируем приведенный выше алгоритм следующим образом:

Вместо очереди будем использовать дек (или можно даже steque). Если рассматриваемое ее ребро имеет вес [math] 0 [/math], то будем добавлять вершину в начало, а иначе в конец. После этого добавления, дополнительный введенный инвариант в доказательстве расположения элементов в деке в порядке неубывания продолжает выполняться, поэтому порядок в деке сохраняется. И, соответственно, релаксируем расстояние до всех смежных вершин и, при успешной релаксации, добавляем их в дек.

Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант расположения элементов в деке в порядке неубывания сохраняется. Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного BFS.

1-k BFS

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

См. также

Источники информации