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