Решение: Кратчайший путь в графе
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Определите кратчайший путь между пунктами A и F при условии, что передвигаться можно только по указанным в таблице дорогам. Каждый пункт можно посетить только один раз.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 3 | |||||
| B | 3 | 2 | 7 | |||
| C | 2 | 2 | ||||
| D | 1 | 1 | ||||
| E | 2 | 1 | 3 | |||
| F | 7 | 1 | 3 |
Решение по шагам
3 шагаИз пункта A можно попасть только в пункт B, поэтому первый участок кратчайшего пути имеет длину 3.
$$A\to B: 3$$Путь A–B–C–E–D–F проходит через каждый пункт не более одного раза и соединяет A с F.
$$3+2+2+1+1=9$$Другие допустимые пути имеют большую длину, например A–B–F имеет длину $3+7=10$. Следовательно, найденный путь является кратчайшим.
Где здесь ошибаются
Выбирать путь с наименьшим количеством дорог, а не с наименьшей суммарной протяжённостью.
Забывать учитывать ограничение: каждый пункт можно посетить только один раз.
Складывать только часть рёбер пути.