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

Задание:

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

Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E и не проходящего через пункт B. Передвигаться можно только по указанным дорогам.

Решение:

1) поскольку нас интересуют только маршруты, НЕ проходящие через пункт В, столбец и строку, соответствующие этому пункту, можно удалить из таблицы:

2) для дальнейшего решения необходимо построить граф типа «дерево»; причем из всех маршрутов нужно оставить только те, которые проходят через пункт Е

3) первый шаг от А (в скобках указаны длины маршрутов):  АС (4), AD (8) прямой маршрут AF не рассматриваем, потому что он не проходит через пункт E

4) второй шаг:  ACD (7), ADC (11), ADE (13) маршрут ADF не рассматриваем, потому что он не проходит через пункт E

5) третий шаг:  ACDE (12), ADEF (18)
маршрут ADEF дошел до пункта назначения;
маршрут ADC продолжать не имеет смысла, потому что из C можно проехать только в пункты A и D, где мы уже были;
маршрут ACDF не рассматриваем, потому что он не проходит через пункт E

6) четвертый шаг: ACDEF(17)

7) этот маршрут тоже дошел до пункта назначения, его длина меньше, чем для предыдущего, его и выбираем

Ответ: 17