Задание 3. Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице: | | A | B | C | D | E | |---|---|---|---|---|---| | A | | 1 | 2 | 2 | 7 | | B | 1 | | 2 | | | | C | 2 | 2 | | 4 | 3 | | D | 2 | | 4 | | | | E | 7 | | 3 | | | Определите длину кратчайшего пути между пунктами А и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. 1) 5 2) 6 3) 7 4) 8

Задание 3. Кратчайший путь между пунктами А и Е

Цель: Найти кратчайший путь из пункта А в пункт Е, используя данные таблицы.

Таблица расстояний:

Поиск путей из А в Е:

Будем использовать алгоритм Дейкстры или просто перебирать возможные пути, суммируя расстояния.

Пути из А:

• A → E: прямое расстояние = 7
• A → B → ... → E:
• A → B: 1
• A → B → C: 1 + 2 = 3
• A → B → C → E: 1 + 2 + 3 = 6
• A → C → ... → E:
• A → C: 2
• A → C → E: 2 + 3 = 5
• A → C → D → ... : D не ведет напрямую к E.
• A → D → ... → E:
• A → D: 2
• A → D → C → E: 2 + 4 + 3 = 9

Сравним найденные пути:

• Прямой путь: 7
• Путь через B: A → B → C → E = 6
• Путь через C: A → C → E = 5
• Путь через D: A → D → C → E = 9

Кратчайший путь: A → C → E, его длина равна 5.

Ответ: 1) 5