Задача 4: Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами А и Е, проходящего через пункт С. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.

Для решения этой задачи нужно рассмотреть все возможные пути из А в Е через С и выбрать самый короткий. Путь 1: A - C - E Длина пути: AC + CE = 30 + 0 (нет прямого пути из C в E). Нужно искать другие варианты. Путь 2: A - C - B - E Длина пути: AC + CB + BE = 30 + 15 + 15 = 60 Путь 3: A - D - C - E Длина пути: AD + DC + CE = 25 + 20 + 0 (нет прямого пути из C в E). Нужно искать другие варианты. Путь 4: A - D - C - B - E Длина пути: AD + DC + CB + BE = 25 + 20 + 15 + 15 = 75 Путь 5: A - B - C - E Длина пути: AB + BC + CE = 5 + 15 + 0 (нет прямого пути из C в E). Нужно искать другие варианты. Путь 6: A - B - C - D - E Длина пути: AB + BC + CD + DE = 5 + 15 + 20 + 10 = 50 Сравним длины путей, проходящих через С: A - B - C - D - E (50) и A - C - B - E (60) Кратчайший путь: A - B - C - D - E, длина которого равна 50. Ответ: 50