Ва­ри­ан­ты марш­ру­тов:

A-B-C-E-F. Длина марш­ру­та 4 + 6 + 4 + 5 = 19

A-B-D-E-F. Длина марш­ру­та 4 + 3 + 2 + 5 = 14

A-B-E-F. Длина марш­ру­та 4 + 6 + 5 = 15

Видно, что крат­чай­ший путь равен 14.

Со­ста­вим марш­рут сле­ду­ю­щим об­ра­зом: стар­туя из пунк­та А, будем все­гда вы­би­рать тот пункт, рас­сто­я­ние до ко­то­ро­го наи­мень­шее. По­лу­чим марш­рут A—B—D—C—E—G, его длина равна 24 км. Те­перь, на­чи­ная с конца марш­ру­та, будем из­ме­нять путь, поль­зу­ясь сле­ду­ю­щим со­об­ра­же­ни­ем: если рас­сто­я­ние, на­при­мер, C—E—G боль­ше рас­сто­я­ния C—G, то за­ме­ня­ем уча­сток марш­ру­та C—E—G на C—G.

A—D—C—E—G: длина марш­ру­та 23 км.

Любое дру­гое из­ме­не­ние пути, через ко­то­рые про­хо­дит марш­рут, при­во­дит к уве­ли­че­нию его длины.

Ответ: 23 км.

За­ме­тим, что в Е можно по­пасть толь­ко из D и F, сле­до­ва­тель­но, в марш­ру­те также обя­за­тель­но дол­жен при­сут­ство­вать пункт D. Со­ста­вим марш­рут сле­ду­ю­щим об­ра­зом: стар­туя из пунк­та А, будем все­гда вы­би­рать тот пункт, рас­сто­я­ние до ко­то­ро­го наи­мень­шее. По­лу­чим марш­рут A—B—D—E—F, его длина равна 2 + 3 + 5 + 5  =  15 км. Те­перь, на­чи­ная с на­ча­ла марш­ру­та, будем из­ме­нять путь, поль­зу­ясь сле­ду­ю­щим со­об­ра­же­ни­ем: если рас­сто­я­ние, на­при­мер, A—B—D боль­ше рас­сто­я­ния A—D, то за­ме­ня­ем уча­сток марш­ру­та A—B—D на A—D. По­про­бо­вав про­из­ве­сти все такие за­ме­ны, по­лу­чим, что марш­рут A—B—D—E—F  — самый ко­рот­кий из тех, что удо­вле­тво­ря­ют усло­вию за­да­чи.

Любое дру­гое из­ме­не­ние пути, через ко­то­рые про­хо­дит марш­рут, при­во­дит к уве­ли­че­нию его длины.

Ответ: 15.

Найдём все ва­ри­ан­ты марш­ру­тов из A в G и вы­бе­рем самый ко­рот­кий.

A−B−C−D−E−G. Длина марш­ру­та 22.

A−B−C−D−F−G. Длина марш­ру­та 22.

A−B−C−G. Длина марш­ру­та 15.

A−B−D−E−G. Длина марш­ру­та 19.

A−B−D−F−G. Длина марш­ру­та 19.

A−D−B−C−G. Длина марш­ру­та 22.

A−D−C−G. Длина марш­ру­та 15.

A−D−F−G. Длина марш­ру­та 20.

A−D−E−G. Длина марш­ру­та 20.

A−B−D−С−G. Длина марш­ру­та 14.

Крат­чай­ший путь равен 14.

Ответ: 14.

При­ве­дем дру­гое ре­ше­ние.

Будем по­сле­до­ва­тель­но на­хо­дить длину са­мо­го ко­рот­ко­го марш­ру­та до каж­до­го из пунк­тов и вы­би­рать тот пункт, крат­чай­ший марш­рут до ко­то­ро­го будет самым ко­рот­ким, до тех пор, пока вы­бран­ным не ока­жет­ся ко­неч­ный пункт G. Ре­зуль­та­ты будем за­пи­сы­вать в таб­ли­цу. За­ме­тим, что при ре­ше­нии на бу­ма­ге не нужно будет каж­дый раз пе­ре­ри­со­вы­вать таб­ли­цу, до­ста­точ­но будет за­чер­ки­вать ста­рую длину марш­ру­та и за­ме­нять ее новой при не­об­хо­ди­мо­сти. Такое ре­ше­ние не тре­бу­ет пе­ре­бо­ра всех воз­мож­ных путей.

Най­дем длину марш­ру­та до каж­до­го из пунк­тов при дви­же­нии не­по­сред­ствен­но из пунк­та А и вы­бе­рем пункт с самым ко­рот­ким марш­ру­том:

Бли­жай­шим к А пунк­том яв­ля­ет­ся пункт В, длина марш­ру­та до него до него 2 км, путь А−В. За­пом­ним этот марш­рут.

Най­дем длину марш­ру­та до каж­до­го пунк­та при дви­же­нии из пунк­та В, для этого сло­жим длину марш­ру­та до пунк­та В и длину пути из В до за­дан­но­го пунк­та. При этом, если длина марш­ру­та до за­дан­но­го пунк­та ока­жет­ся ко­ро­че, чем ранее най­ден­ная, то ранее най­ден­ную длину за­ме­ним на эту более ко­рот­кую. Вы­бе­рем пункт с самым ко­рот­ким (после В) марш­ру­том:

Пункт с самым ко­рот­ким (после В) марш­ру­том  — это D, путь А-В-D дли­ной 5 км, за­пом­ним его.

Най­дем длину марш­ру­та до каж­до­го пунк­та при дви­же­нии из пунк­та D, для этого сло­жим длину марш­ру­та до пунк­та D и длину пути из D до за­дан­но­го пунк­та. При этом, если длина марш­ру­та до за­дан­но­го пунк­та ока­жет­ся ко­ро­че, чем ранее най­ден­ная, то ранее най­ден­ную длину за­ме­ним на эту более ко­рот­кую. Вы­бе­рем пункт с самым ко­рот­ким (после D) марш­ру­том:

Пункт с самым ко­рот­ким (после D) марш­ру­том  — это C, путь А-В-D-C дли­ной 6 км, за­пом­ним его.

Най­дем длину марш­ру­та до каж­до­го пунк­та при дви­же­нии из пунк­та С, для этого сло­жим длину марш­ру­та до пунк­та С и длину пути из С до за­дан­но­го пунк­та. При этом, если длина марш­ру­та до за­дан­но­го пунк­та ока­жет­ся ко­ро­че, чем ранее най­ден­ная, то ранее най­ден­ную длину за­ме­ним на эту более ко­рот­кую. Вы­бе­рем пункт с самым ко­рот­ким (после С) марш­ру­том:

Пункт с самым ко­рот­ким (после C) марш­ру­том  — это F, путь А-В-D-F дли­ной 12 км, за­пом­ним его.

Най­дем длину марш­ру­та до каж­до­го пунк­та при дви­же­нии из пунк­та F, для этого сло­жим длину марш­ру­та до пунк­та F и длину пути из F до за­дан­но­го пунк­та. При этом, если длина марш­ру­та до за­дан­но­го пунк­та ока­жет­ся ко­ро­че, чем ранее най­ден­ная, то ранее най­ден­ную длину за­ме­ним на эту более ко­рот­кую. Вы­бе­рем пункт с самым ко­рот­ким (после F) марш­ру­том:

Пунк­ты с самым ко­рот­ким (после F) марш­ру­том  — это E и G.

Сле­до­ва­тель­но, самый ко­рот­кий марш­рут до пунк­та G со­став­ля­ет 14 км.

За­ме­тим, что длина марш­ру­та до пунк­та G, рав­ная 14 км, была най­де­на на одном из преды­ду­щих шагов, при рас­смот­ре­нии дви­же­ния из пунк­та С. Но при этом имел­ся пункт, марш­рут до ко­то­ро­го был ко­ро­че (пункт F). Если бы из F в G была до­ро­га про­тя­жен­но­стью 1 км, то до пунк­та G на­шел­ся бы более ко­рот­кий марш­рут. По­это­му на­хож­де­ние марш­ру­тов долж­но вы­пол­нять­ся до тех пор, пока марш­рут до ис­ко­мо­го пунк­та не ока­жет­ся самым ко­рот­ким из тех, ко­то­рые не были вы­бра­ны и за­пом­не­ны ранее.

Найдём все ва­ри­ан­ты марш­ру­тов из A в G и вы­бе­рем самый ко­рот­кий.

Из пунк­та A можно по­пасть в пунк­ты B и D.

Из пунк­та B можно по­пасть в пунк­ты C и D.

Из пунк­та C можно по­пасть в пунк­ты D и G.

Из пунк­та D можно по­пасть в пунк­ты E и F.

Из пунк­та E можно по­пасть в пункт G.

Из пунк­та F можно по­пасть в пункт G.

A−B−C−D−E−G. Длина марш­ру­та 18.

A−B−C−D−F−G. Длина марш­ру­та 25.

A−B−C−G. Длина марш­ру­та 15.

A−B−D−E−G. Длина марш­ру­та 11.

A−B−D−F−G. Длина марш­ру­та 18.

A−D−F−G. Длина марш­ру­та 20.

A−D−E−G. Длина марш­ру­та 13.

Крат­чай­ший путь равен 11.

Ответ: 11.