Изменения

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