Изменения

Оба инварианта сохранились, <tex> \Rightarrow </tex> после любого шага алгоритма элементы в очереди элементы неубывают .

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