Найдём все ва­ри­ан­ты марш­ру­тов из 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 на­шел­ся бы более ко­рот­кий марш­рут. По­это­му на­хож­де­ние марш­ру­тов долж­но вы­пол­нять­ся до тех пор, пока марш­рут до ис­ко­мо­го пунк­та не ока­жет­ся самым ко­рот­ким из тех, ко­то­рые не были вы­бра­ны и за­пом­не­ны ранее.