Question

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

Answer 1

Из города А можно попасть в города B-2, C-4, D-8, F-16.

16 - многовато. Поищем другие пути.

Если учесть, что мне не возвращаемся в посещенные точки, то всего можно насчитать 7 путей:

• A-F = 16
• A-C-D-E-F = 17
• A-B-D-F = 8
• A-D-E-F = 18
• A-D-F = 11
• A-B-D-E-F = 15
• A-C-D-F = 10

Оставляем только пути, которые проходят через точку E:

• A-C-D-E-F = 17
• A-D-E-F = 18
• A-B-D-E-F = 15

Рассчитывая стоимость путей, получаем, что минимальная длина пути = 15. (путь A-B-D-E-F).

Ответ: 15

==============

Если ответ устроил, то не забудь отметить его как "Лучший".

==============