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

Для решения этой задачи составим таблицу или граф, отображающий все возможные пути из пункта А в пункт Е, исключая пункт F.

Пункты и расстояния:

• A-B: 7
• A-C: 4
• A-D: 8
• B-C: 3
• B-E: 2
• C-D: 3
• C-E: 8
• D-E: 5
• D-F: 3
• E-F: 8

Кратчайший путь из А в Е, не проходящий через F:

Рассмотрим все возможные пути из А в Е, исключая F:

1. A → B → E: 7 + 2 = 9
2. A → C → E: 4 + 8 = 12
3. A → D → E: 8 + 5 = 13
4. A → B → C → E: 7 + 3 + 8 = 18
5. A → C → D → E: 4 + 3 + 5 = 12
6. A → D → C → E: 8 + 3 + 8 = 19 (путь A → D → C → E)

Сравнивая длины всех путей, находим кратчайший.

Кратчайший путь: A → B → E, длина 9.

Ответ: 9