Изменения

Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от <tex> s </tex> найдены некорректно, ту, длина найденного расстояния до которой минимальна. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в кратчайшем пути до <tex> u </tex> — вершина <tex> w </tex>. Расстояние  Пусть <tex> s{w_1}{w_2}{\ldots}wu </tex> - этот кратчайший путь. Понятно, что <tex> s{w_1}{w_2}{\ldots}w </tex> - кратчайший путь до <tex> w </tex> (если бы он не был кратчайшим, то можно было бы заменить его на кратчайший в пути до вершин <tex> v u </tex>, значит, путь до <tex> u </tex> — тоже не кратчайший). Вес каждого ребра равен 1, значит, <tex> d[u] > \rho(s, u) = d[w] + 1 </tex> , и <tex> d[w ] < d[u] </tex> найдено корректно(по выбору вершины . Неравенство <tex> d[v] < d[u] </tex> следует из того, что <tex> v </tex> — предок <tex> u </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> в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.