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

Решение: Необходимо найти кратчайший путь из пункта A в пункт F, проходящий через пункт D. Рассмотрим возможные пути через D и выберем кратчайший: 1. Путь A → D → F * Длина пути A → D = 10 км * Длина пути D → F = 5 км * Общая длина пути A → D → F = 10 + 5 = 15 км 2. Путь A → B → D → F * Длина пути A → B = 5 км * Длина пути B → D = 4 км * Длина пути D → F = 5 км * Общая длина пути A → B → D → F = 5 + 4 + 5 = 14 км 3. Путь A → C → D → F * Длина пути A → C = 8 км * Длина пути C → D = Нет прямого пути 4. Путь A → D → E → F * Длина пути A → D = 10 км * Длина пути D → E = Нет прямого пути 5. Путь A → B → C → D → F * Длина пути A → B = 5 км * Длина пути B → C = Нет прямого пути 6. Путь A → B → E → D → F * Длина пути A → B = 5 км * Длина пути B → E = Нет прямого пути 7. Путь A → D → B → F * Длина пути A → D = 10 км * Длина пути D → B = 4 км * Длина пути B → F = Нет прямого пути 8. Путь A -> D -> E -> F * Длина пути А -> D = 10 км * Длина пути D -> E = Нет прямого пути 9. Путь А -> В -> Е -> F * Длина пути А -> В = 5 км * Длина пути В -> Е = Нет прямого пути Рассмотрим еще варианты обходных путей с использованием промежуточных пунктов. Таким образом, кратчайший путь: A → B → D → F = 14 км Ответ: 14