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

Решение:

Рассмотрим возможные пути из пункта А в пункт F и выберем кратчайший:

• A - B - F: 5 + 7 = 12
• A - D - B - F: 3 + 1 + 7 = 11
• A - D - C - F: 3 + 1 + 5 = 9
• A - E - B - F: 3 + 2 + 7 = 12
• A - E - D - C - F: не существует, так как нет дороги E - D
• A - E - F: не существует, так как нет дороги E - F

Самый короткий путь: A - D - C - F = 9

Ответ: 9