Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
| A | B | C | D | E | F | G | |
| A | 2 | 6 | |||||
| B | 2 | 5 | 2 | ||||
| C | 5 | 4 | 8 | ||||
| D | 6 | 2 | 4 | 2 | 7 | ||
| E | 2 | 5 | |||||
| F | 7 | 7 | |||||
| G | 8 | 5 | 7 |
Определите длину кратчайшего пути между пунктами A и 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.