1. Найдите кратчайший путь между пунктами A и D по матрице расстояний: AB = 3, AC = 5, BC = 1, BD = 6, CD = 4, CE = 1, DE = 3.

Сравним пути от A до D. Через B и C получаем путь A—B—C—D длиной 3 + 1 + 4 = 8. Другой вариант A—C—D имеет длину 5 + 4 = 9; путь A—B—D — 3 + 6 = 9.

Ответ: кратчайший путь A—B—C—D, его длина — 8.