Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Определите кратчайший путь между пунктами A и E (при условии, что передвигаться можно только по построенным дорогам).
1. Укажите длину этого пути
2. Укажите этот маршрут(без пробелов), включая начальный и конечный пункт
Ответы
Ответ:
Объяснение:
Ну тут простой перебор:
Первый пункт А. Смотрим куда мы можем попасть:
Пункт Е - хорошо, запоминаем маршрут и записываем число 9.
Пункт D - запоминаем число 5.
Пункт А - опять число 5, при этом в E мы не попадаем, но при этом у нас имеется более короткий маршрут, значит сразу отбрасываем.
Пункт C - число 3. Общая длинна стала 8.
Пункт B - опять больше 9, при этом в E не попадаем - то есть уже перебор. Отбрасываем.
Пункт D - опять больше 9 и опять отбрасываем.
Пункт E - число 2. При этом мы попадаем в пункт E и длинна маршрута равна 7. Значит наш прошлый маршрут хуже. Хорошо, запоминаем этот и идём дальше.
Пункт B - запоминаем число 2.
Пункт А - тут в сумме путь равен 4, но из здравого смысла, путь, в котором мы возвращаемся в пункт отправления, заведомо не оптимален. По этому это тоже отбрасываем.
Пункт C - тут число 5. Путь равен 7, при этом в пункт E мы не попадаем. Снова отбрасываем.
Пункт E - тут число 1. Общая длинна пути - 3. Мы нашли путь ещё короче чем предыдущий.
Усё, мы все перебрали. Кратчайший путь - A-B-E и его длинна равна 3.