Номер §2.4 ПМ 5

По таблице на с. выпишем дороги, которые могут входить в простой путь через C: A–B = , A–C = , A–D = , B–C = , B–D = , C–D = , D–E = , A–E = . Пункт E должен быть концом пути; заходить в уже посещённый пункт нельзя.

По дереву на с. через C проходят три пути из A в E. Для пути A–B–C–D–E складываем веса всех четырёх дорог: , , . Для пути A–C–D–E получаем , . Для пути A–C–B–D–E получаем , , .

Сравниваем длины: . Путь A–B–D–E имеет длину , но он не проходит через C, поэтому условию не подходит. Искомый путь — A–B–C–D–E, его длина равна .