Между населенными пунктам 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 с подробным решением

anyacotick anyacotick    3   14.03.2019 08:10    2

Ответы
yalunaluna yalunaluna  25.05.2020 06:48

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

 

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

ПОКАЗАТЬ ОТВЕТЫ
Другие вопросы по теме Информатика