2. Между населёнными пунктами A, B, C, D, E, F построены дороги. Их протяжённость: A–C — 2, A–D — 1, B–C — 1, B–F — 3, C–F — 4, D–E — 1, D–F — 4, E–F — 5. Определите длину кратчайшего пути между пунктами A и F, если передвигаться можно только по построенным дорогам.

Сравним пути, ведущие из A в F.

1. По маршруту A–D–F длина равна \(1+4=5\).
2. По маршруту A–C–F длина равна \(2+4=6\).
3. По маршруту A–C–B–F длина равна \(2+1+3=6\).

Маршрут A–D–F короче рассмотренных альтернатив.

Ответ: 5.