304
правки
Изменения
→Обоснование корректности
== Обоснование корректности ==
Пусть <tex>p(u, v)</tex> — длина кратчайшего пути из вершины <tex>u</tex> в вершину <tex>v</tex>. Докажем по индукции, что в момент посещения любой вершины <tex>u</tex>, <tex>d(u)=p(s,u)</tex>, где <tex>s</tex> - стартовая вершина.
== Оценка сложности ==
