35
правок
Изменения
→Корректность
В алгоритме поиска в ширину очередь всегда содержит сначала некоторое количество вершин с расстоянием k, а потом некоторое количество вершин с расстоянием k + 1(возможно, нулевое).
|proof=
Докажем это утверждение индукцией по шагам алгоритмачислу выполненных алгоритмом шагов.
База: изначально очередь содержит только одну вершину <tex> s </tex> с расстоянием 0, утверждение верно.
Алгоритм поиска в ширину в невзвешенном графе находит оптимальные расстояния до всех достижимых вершин.
|proof=
Допустим, что это не так. Выберем из вершин, для которых найдено неоптимальное расстояние от <tex> s </tex> ту, которая находится на минимальном расстояниидлина кратчайшего пути до которой минимальна. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предкок предок в оптимальном пути до <tex> v </tex> — вершина <tex> w </tex>. Расстояние до вершин <tex> v </tex> и <tex> w </tex> найдено корректно, путь через <tex> w </tex> оптимальный, а через <tex> v </tex> — нет, поэтому <tex> d[w] < d[v] </tex>. Из ранее доказанной леммы следует, что в этом случае вершина <tex> w </tex> попала в очередь и была обработана раньше, чем <tex> v </tex>. Но она соединена с <tex> u </tex>, значит, <tex> v </tex> не может быть предком <tex> u </tex> в дереве обхода в ширину, мы пришли к противоречию, и следовательно найденные расстояния до всех вершин оптимальны.
}}
