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

Определим длину кратчайшего пути между пунктами А и F, не проходящего через пункт Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.

Пути из А в F, не проходящие через Е:

1. A-G-B-C-F = 2 + 4 + 1 = 8
2. A-G-B-D-F = 2 + 0 + 5 = 7
3. A-D-B-C-F = 1 + 4 + 1 = 6
4. A-D-C-F = 1 + 1 = 2
5. A-D-F = 5
6. A-G-B-D-C-F = 1 + 2 + 0 + 4 + 1 = 8

Кратчайший путь равен 5.

Ответ: 5