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

По таблице доступны дороги: A–C — 8 км, A–D — 10 км, B–D — 4 км, B–E — 1 км, C–D — 1 км, C–E — 3 км.

1. Путь A–C–D–B имеет длину 8 + 1 + 4 = 13 км.
2. Путь A–D–B имеет длину 10 + 4 = 14 км.
3. Путь A–C–E–B имеет длину 8 + 3 + 1 = 12 км.

Путь через E короче рассмотренных альтернатив; пути с дополнительными дорогами не дают меньшей длины.

Ответ: 12 км.