Решение: Кратчайший путь между пунктами
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами B и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 1 | 2 | 4 | ||
| B | 1 | 4 | |||
| C | 2 | 4 | 1 | ||
| D | 4 | ||||
| E | 4 | 1 | 4 |
Решение по шагам
4 шагаПункт D соединён только с пунктом E, поэтому путь из B в D должен заканчиваться переходом E–D длиной 4 км.
Рассмотрим маршрут B–A–C–E–D. Все пункты в нём различны, а длина маршрута равна:
$$1+2+1+4=8$$Другой возможный маршрут B–C–E–D имеет длину $4+1+4=9$ км. Маршрут B–A–E–D также длиннее: $1+4+4=9$ км.
Следовательно, кратчайший путь имеет длину 8 км.
Где здесь ошибаются
Не учитывают возможность пройти из B через A и C.
Складывают длины дорог маршрута, посещая один и тот же пункт повторно.
Выбирают путь B–C–E–D длиной 9 км, не сравнив его с маршрутом B–A–C–E–D.