Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
| A | B | C | D | E | F | |
| A | 2 | 4 | 8 | 16 | ||
| B | 2 | 3 | ||||
| C | 4 | 3 | ||||
| D | 8 | 3 | 3 | 2 | 3 | |
| E | 2 | 5 | ||||
| F | 16 | 3 | 5 |
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E. Передвигаться можно только по указанным дорогам.
Заметим, что в Е можно попасть только из D и F, следовательно, в маршруте также обязательно должен присутствовать пункт D. Составим маршрут следующим образом: стартуя из пункта А, будем всегда выбирать тот пункт, расстояние до которого наименьшее. Получим маршрут A—B—D—E—F, его длина равна 12 км. Теперь, начиная с начала маршрута, будем изменять путь, пользуясь следующим соображением: если расстояние, например, A—B—D больше расстояния
Любое другое изменение пути, через которые проходит маршрут, приводит к увеличению его длины.
Ответ: 12.
Путь A-B-D-F, случайно, не будет равняться 8?????
Обратите внимание, что нужно найти такой путь, который проходит через пункт Е.
Разве здесь не 10? F(3)>E(2)>B(3)>A(2)=10
Между пунктами E и B дороги не существует.