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

Составим таблицу с расстояниями между пунктами и будем искать кратчайший путь из A в F через E: | Откуда | Куда | Расстояние | | :----- | :----- | :--------- | | A | C | 7 | | A | D | 3 | | A | F | 12 | | B | E | 4 | | B | F | 9 | | C | A | 7 | | C | E | 6 | | D | A | 3 | | D | E | 8 | | D | F | 4 | | E | B | 4 | | E | C | 6 | | E | D | 8 | | E | F | 15 | | F | A | 12 | | F | B | 9 | | F | D | 4 | | F | E | 15 | Возможные пути из A в F через E: 1. A -> F: Расстояние = 12 (но этот путь не проходит через E) 2. A -> C -> E -> F: Расстояние = 7 + 6 + 15 = 28 3. A -> D -> E -> F: Расстояние = 3 + 8 + 15 = 26 4. A -> D -> F: Расстояние = 4 (но этот путь не проходит через E) 5. A -> C -> E -> B -> F: Расстояние = 7 + 6 + 4 + 9 = 26 6. A -> D -> E -> B -> F: Расстояние = 3 + 8 + 4 + 9 = 24 Кратчайший путь: A -> D -> E -> B -> F, его длина 24. Ответ: 24