Между населенными пунктам A,B,C,D,E,F,Z построены дороги протяженность которых приведена...

Question

Между населенными пунктам A,B,C,D,E,F,Z построены дороги протяженность которых приведена в таблице(отсутствие числа в таблице означает, что прямой дороги между пунктами нет)

A B C D E F Z

A 7 57

B 7 5 7 27

C 5 3

D 7 3 2

E 27 2 2 8

F 2 3

Z 57 8 3

Определить длину кратчайшего пути между пунктами AиZ (при условии что передвигаться можно только по построенным дорогам)
1)21
2)24
3)42
4) 57
Пожалуйста с подробным решением

Answer 1

1) Из А только два пути - AB=7, AZ=57.

AZ слишком большой, для начала отбросим его.

Идём по AB=7.

 

2) Из B три пути: BC=5, BD=7, BE=27.

BE слишком большой, пока отбросим его.

2.1) Рассмотрим для BC=5 :

Из C есть только один путь, CD=3.

Рассмотрим для CD :

Из D есть DB, но нам незачем возвращаться; значит остаётся DE=2.

Рассмотрим для DE :

Из Е есть EB, но это возврат, есть EF=2 и EZ=8

2.1.1) Если мы идём по EF, то от F есть FZ=3

В итоге, получается: A-B-C-D-E-F-Z = 7+5+3+2+2+3 = 22

2.1.2) Если в предпоследнем шаге пойти по EZ=8, то получается A-B-C-D-E-Z = 7+5+3+2+8 = 25

 

2.2) Рассмотрим для BD=7

Этим шагом мы как бы перескочим B-C-D

Из D есть DC и DE, идти в С нет смысла, так что идём в DE=2

Из Е есть EF=2 и EZ=8

2.2.1) Для начала пойдём в EF=2, FZ=3

Получается A-B-D-E-F-Z = 7+7+2+2+3 = 21

 

2.2.2) Другой вариант, EZ=8

Получается A-B-D-E-Z = 7+7+2+8 =24

 

Ответ уже найдет, выделен жирным, но в других задачах иногда нужно просмотреть абсолютно все пути.