Между населенными пунктам 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
Пожалуйста с подробным решением
Answers & Comments
Verified answer
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
Ответ уже найдет, выделен жирным, но в других задачах иногда нужно просмотреть абсолютно все пути.