Ответы
Ответ:
9
Объяснение:
Из пункта А можно попасть в пункты B, D и G. Поскольку нам необходимо найти кратчайший путь между A и G, то дорогу А-G можно сразу откинуть и установить как максимум, т.к. если любой другой ответ будет больше A-G, то не имеет смысла идти через другие населённые пункты.
Получается наши варианты на данный момент это A-B или A-D, ни в один из этих пунктов (B, D) нельзя попасть прямиком из пункта G.
Из пункта G мы можем попасть в C, E, F. При этом все эти пути равноценны для нас, т.к. все они равны 3.
Поскольку A-D равен 1, а A-B равен 4, то рассмотрим далее пункты D, т.к. для нас пока что этот путь выгоднее.
Из пункта D мы можем попасть в пункты B и C, но пункт B нам не нужен, т.к. мы можем туда из пункта А, да и из пункта B можно попасть только или в А или D.
Значит, пока что первый наш маршрут это A-D-C-G, что 1+5+3 = 9.
Посмотрим что может получится из пути A-B.
Попав в пункт B мы можем попасть дальше только в пункт D, то есть ничего далее не меняется, а значит нам надо просто сравнить стоимость пути до пункта D.
A-D = 1.
A-B-D = 5.
Получается A-D-C-G наиболее оптимальный и короткий.
Ещё один вариант рассуждения это посмотреть какие варианты пути доступны E, F и C, пути до которых для нас равноценны из пункта G.
Мы увидим, что из E и F можно попасть только в С, то есть для нас не имеет смысла идти в любой другой пункт из G кроме как в C.
Надеюсь, что понятна общая логика и последовательность :)