1679
правок
Изменения
→Корректность
{{Утверждение
|statement=
В алгоритме очереди поиска в ширину очередь всегда содержит сначала некоторое количество расстояние вершин с расстоянием k, а потом некоторое количество вершин с расстоянием k + 1 (возможно, нулевое)монотонно неубывает.
|proof=
Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.
