Графы: оптимальный путь:
Жаль, что замок не летает! Придётся ездить только по отмеченным дорогам.
В матрице смежности указаны расстояния между городами Бразилии.
Найди кратчайший путь от Бразилиа до Патус-ди-Минас. Запиши его длину.
1 Ответ
Решение:
Попробуем кратчайшие маршруты по таблице:
Бразилиа → Кристалина (130) → Уберландия (300) → Патус-ди-Минас (220)
Сумма: 130 + 300 + 220 = 650
Бразилиа → Кристалина (130) → Луисландия-ду-Уэсти (290) → Патус-ди-Минас (150)
Сумма: 130 + 290 + 150 = 570
Бразилиа → Анаполис (170) → Гония (60) → Итумбиара (210) → Уберландия (150) → Патус-ди-Минас (220)
Сумма: 170 + 60 + 210 + 150 + 220 = 810 (длиннее)
Других связей для короткого пути нет (например, напрямую Бразилиа–Луисландия нет).
Кратчайший найденный путь:
Бразилиа → Кристалина (130) → Луисландия-ду-Уэсти (290) → Патус-ди-Минас (150)
Длина = 570 км.
Ответ: 570