Изменения

Оценим время работы для входного графа <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>.

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

'''int''' '''BFS'''(EG: <(V, E>), source: '''int''', destination: '''int''') d = '''int'''[|V|] d.'''fill'''(d, <tex> \infty </tex>)

d[v] = d[qu] + 1

Пусть в графе разрешены ребра целочисленного веса из отрезка <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| + k|E|) </tex>.