Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
| A | B | C | D | E | F | |
| A | 4 | 8 | 24 | |||
| B | 4 | 3 | ||||
| C | 8 | 3 | 3 | 8 | 14 | |
| D | 3 | 12 | ||||
| E | 8 | 5 | ||||
| F | 24 | 14 | 12 | 5 |
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
Найдём все варианты маршрутов из A в F и выберем самый короткий.
В пункт F можно попасть из пунктов A,C,D и Е.
В пункт D и Е можно попасть из пункта С.
В пункты С можно попасть только из пунктов А и В.
В пункт B можно попасть только из пункта А.
A-B-C-D-F. Длина маршрута 4 + 3 + 3 + 12 = 22.
A-B-C-E-F. Длина маршрута 4 + 3 + 8 + 5 = 20.
A-B-C-F. Длина маршрута 4 + 3 + 14 = 21.
A-C-E-F. Длина маршрута 8 + 8 + 5 = 21.
A-C-D-F. Длина маршрута 8 + 3 + 12 = 23.
A-C-F. Длина маршрута 8 + 14 = 22.
Видно, что кратчайший путь равен 20.