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

Решение:

Нам нужно найти кратчайший путь из А в В через Е. Это означает, что путь будет иметь вид A → ... → E → ... → B. Так как каждый пункт можно посетить только один раз, то путь будет состоять из двух частей: кратчайший путь из А в Е и кратчайший путь из Е в В.

Построим таблицу для поиска кратчайших путей (алгоритм Дейкстры):

Кратчайший путь из A в E:

• A → E: длина 1

Кратчайший путь из E в B:

• E → B: длина 2

Общая длина пути A → E → B составляет \( 1 + 2 = 3 \).

Проверим другие возможные пути через Е:

• A → C → E → B: \( 1 + 2 + 2 = 5 \)
• A → D → E → B: \( 1 + 1 + 2 = 4 \)
• A → B (напрямую): не проходит через E.

Наименьший путь из A в B через E - это A → E → B.

Ответ: 3