Задание 2. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

Из таблицы видны дороги: A–B — 9, A–C — 2, A–D — 1, A–E — 4, A–F — 5, B–C — 2, C–D — 4, D–E — 1, E–F — 1.

Проверим короткие пути от A до F:

1. A–F: длина 5.
2. A–E–F: 4 + 1 = 5.
3. A–D–E–F: 1 + 1 + 1 = 3.
4. A–C–D–E–F: 2 + 4 + 1 + 1 = 8.

Путь A–D–E–F короче прямой дороги A–F и остальных путей, которые могут лишь добавить неотрицательную длину.

Ответ: 3.