Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами А и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.

Рассмотрим все возможные пути из A в D, не посещая один пункт более одного раза, и выберем кратчайший: 1. A - B - C - D: 10 + 10 + 9 = 29 2. A - B - E - D: 10 + 1 + 7 = 18 3. A - C - D: 20 + 9 = 29 4. A - C - E - D: 20 + 1 + 7 = 28 5. A - E - D: 20 + 7= 27 Из перечисленных путей самый короткий путь A - B - E - D с длиной 18 км.