689
правок
Изменения
вопросы по правке статьи
К последним замечаниям:
* ''Оставшиеся "Оптимальные расстояния/пути" заменить на "длины кратчайших путей"''
: Заменил, но не понимаю, чем плохо слово "оптимальный"? Там, где имелся в виду сам путь, а не его длина, оставил что-то вроде "кратчайший путь".
* ''В теореме о корректности не ясно, почему до w расстояние найдено верно, ведь из того, что w - предок u в кратчайшем пути не следует, что d[w] < d[u]''
: По-моему, это очевидно. Пусть <tex> s{w_1}{w_2}{\ldots}wu </tex> - этот кратчайший путь. Понятно, что <tex> s{w_1}{w_2}{\ldots}w </tex> - кратчайший путь до <tex> w </tex> (если бы он был не кратчайшим, то можно было бы заменить его на кратчайший в пути до <tex> u </tex>, значит, путь до <tex> u </tex> тоже не кратчайший). Мы рассматриваем невзвешенный граф, поэтому вес каждого ребра равен 1. Значит, <tex> d[u] = d[w] + 1 </tex>. Если нужно, могу добавить эти соображения в статью, если я неправ, то объясните, пожалуйста, в чем именно.
--[[Участник:Sementry|Мейнстер Д.]] 05:48, 17 ноября 2011 (MSK)
* ''Оставшиеся "Оптимальные расстояния/пути" заменить на "длины кратчайших путей"''
: Заменил, но не понимаю, чем плохо слово "оптимальный"? Там, где имелся в виду сам путь, а не его длина, оставил что-то вроде "кратчайший путь".
* ''В теореме о корректности не ясно, почему до w расстояние найдено верно, ведь из того, что w - предок u в кратчайшем пути не следует, что d[w] < d[u]''
: По-моему, это очевидно. Пусть <tex> s{w_1}{w_2}{\ldots}wu </tex> - этот кратчайший путь. Понятно, что <tex> s{w_1}{w_2}{\ldots}w </tex> - кратчайший путь до <tex> w </tex> (если бы он был не кратчайшим, то можно было бы заменить его на кратчайший в пути до <tex> u </tex>, значит, путь до <tex> u </tex> тоже не кратчайший). Мы рассматриваем невзвешенный граф, поэтому вес каждого ребра равен 1. Значит, <tex> d[u] = d[w] + 1 </tex>. Если нужно, могу добавить эти соображения в статью, если я неправ, то объясните, пожалуйста, в чем именно.
--[[Участник:Sementry|Мейнстер Д.]] 05:48, 17 ноября 2011 (MSK)
