Обсуждение:Обход в ширину
К последним замечаниям:
- Оставшиеся "Оптимальные расстояния/пути" заменить на "длины кратчайших путей"
- Заменил, но не понимаю, чем плохо слово "оптимальный"? Там, где имелся в виду сам путь, а не его длина, оставил что-то вроде "кратчайший путь".
- В теореме о корректности не ясно, почему до w расстояние найдено верно, ведь из того, что w - предок u в кратчайшем пути не следует, что d[w] < d[u]
- По-моему, это очевидно. Пусть - этот кратчайший путь. Понятно, что - кратчайший путь до (если бы он был не кратчайшим, то можно было бы заменить его на кратчайший в пути до , значит, путь до тоже не кратчайший). Мы рассматриваем невзвешенный граф, поэтому вес каждого ребра равен 1. Значит, . Если нужно, могу добавить эти соображения в статью, если я неправ, то объясните, пожалуйста, в чем именно.
--Мейнстер Д. 05:48, 17 ноября 2011 (MSK)
