Обсуждение:Обход в ширину

К последним замечаниям:

• Оставшиеся "Оптимальные расстояния/пути" заменить на "длины кратчайших путей"

Заменил, но не понимаю, чем плохо слово "оптимальный"? Там, где имелся в виду сам путь, а не его длина, оставил что-то вроде "кратчайший путь".

• В теореме о корректности не ясно, почему до w расстояние найдено верно, ведь из того, что w - предок u в кратчайшем пути не следует, что d[w] < d[u]

По-моему, это очевидно. Пусть [math] s{w_1}{w_2}{\ldots}wu [/math] - этот кратчайший путь. Понятно, что [math] s{w_1}{w_2}{\ldots}w [/math] - кратчайший путь до [math] w [/math] (если бы он был не кратчайшим, то можно было бы заменить его на кратчайший в пути до [math] u [/math], значит, путь до [math] u [/math] тоже не кратчайший). Мы рассматриваем невзвешенный граф, поэтому вес каждого ребра равен 1. Значит, [math] d[u] = d[w] + 1 [/math]. Если нужно, могу добавить эти соображения в статью, если я неправ, то объясните, пожалуйста, в чем именно.

--Мейнстер Д. 05:48, 17 ноября 2011 (MSK)