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

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