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