Между населёнными пунктами A, B, C, D, E, F построены дороги

Пример задания:

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

1. 9
2. 13
3. 14
4. 15

Решение:

Рассмотрим все возможные пути, по которым можно попасть из пункта A в пункт F:

Из пункта A есть только 1 дорога в пункт B. Из пункта B можно попасть в пункты A, C, D и E, но пункт A нужно исключить, так как мы в нем уже были.

Из пункта C можно попасть только в пункт E (B исключаем). Из пункта E можно попасть в пункты D и F (B и C исключаем). Пункт D также нужно исключить, так как из него можно попасть только в в пункты B и E, где мы уже были. Длина маршрута A – B – C – E – F равна:

Из пункта D можно попасть в пункт E (B исключаем). Из пункта E можно попасть в пункты C и F (B и D исключаем). Пункт C также нужно исключить, так как из него можно попасть только в в пункты B и E, где мы уже были. Длина маршрута A – B – D – E – F равна:

Из пункта E можно попасть только в пункты C, D и F (B исключаем). Пункты C и D также нужно исключить, так как из них можно попасть только в в пункты B и E, где мы уже были. Длина маршрута A – B – E – F равна:

Из 3 маршрутов самым коротким является A – B – D – E – F, его длина равна 14. Таким образом, верным является ответ 3.

Ответ: 3