Изменения
→Замечания:
|statement= Катчайшее дерево путей <tex>T'</tex> в графе <tex>G</tex> можно получить, найдя кратчайшее дерево путей <tex>T</tex> в графе <tex>K</tex>, а затем заменив в нем каждую компоненту связности деревом, построенным из дуг нулевой длинны.
|proof=
:Зафиксируем любое дерево путей и покажем, что в графе <tex>G</tex> найдется дерево не большей длины, имеющее такую структуру, как сказано в лемме. Для такой структуры дерева необходимо и достаточно, чтобы в каждое из подмножеств входило только по одной дугеодному ребру. Меньше быть не может, иначе получится отдельная компонента связности.Если же в какое-то подмножество входит больше чем одна дугаодно ребро, то все дуги ребра кроме одной одного можно заменить дугами ребрами нулевой длины, лежащими внутри подмножества, что разве лишь уменьшит длину дерева и не нарушит связности. Повторяя это преобразование нужное число раз мы добьемся искомой структуры дерева.
}}
