Задача 1 Даны 4 города: А, В, С, D. Из каждого города идут дороги разной длинны: A - В (длина 4) А - С (длина 7) В - С (длина 2) B - D (длина 5) С - D (длина 1) Выполните: Нарисуйте граф дорог (подпишите длины) Найдите кратчайший путь из А в D. Запишите маршрут и длину.

Решение Задачи 1:

1. Построение графа:

   Представим города как вершины графа, а дороги как рёбра, подписанные их длинами:

   Вершины: А, В, С, D

   Рёбра:

   • А-В: 4
   • А-С: 7
   • В-С: 2
   • В-D: 5
   • С-D: 1

   Визуально это можно представить так:

   4 A ---- B | \ / | | \/ | 5 7 2 D | /\ | | / \ | C ----- 1

2. Поиск кратчайшего пути из А в D:

   Рассмотрим все возможные пути из А в D и их длины:

   • Путь 1: А -> В -> D
     Длина: 4 + 5 = 9
   • Путь 2: А -> С -> D
     Длина: 7 + 1 = 8
   • Путь 3: А -> В -> С -> D
     Длина: 4 + 2 + 1 = 7

   Сравнивая длины всех путей, мы видим, что кратчайший путь — это А -> В -> С -> D.

Маршрут: А -> В -> С -> D

Длина: 7