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

Решение:

Для поиска кратчайшего пути между пунктами А и D воспользуемся алгоритмом Дейкстры или методом перебора путей, учитывая, что каждый пункт можно посетить только один раз.

Рассмотрим все возможные пути от А до D, не посещая пункты повторно:

• A → B → C → D: 2 + 3 + 5 = 10 км
• A → C → D: 6 + 5 = 11 км
• A → B → C → E → D: 2 + 3 + 2 + 3 = 10 км
• A → C → E → D: 6 + 2 + 3 = 11 км
• A → D: 8 км

Сравнивая длины всех возможных путей, видим, что кратчайшим является путь A → D.

Ответ: 8