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

По таблице дороги имеют длины: AB = 3, AC = 5, BC = 1, BD = 6, CD = 4, CE = 1, DE = 3.

Проверим пути из A в D:

• A → B → D: 3 + 6 = 9;
• A → C → D: 5 + 4 = 9;
• A → B → C → D: 3 + 1 + 4 = 8;
• A → C → E → D: 5 + 1 + 3 = 9.

Путь A → B → C → D имеет наименьшую длину.

Ответ: 8.