Решение: Кратчайший путь между пунктами
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Определите длину кратчайшего пути между пунктами A и F, если передвигаться можно только по построенным дорогам.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | — | 4 | ||||
| B | 4 | — | 7 | 5 | 7 | |
| C | 7 | — | 5 | |||
| D | 5 | — | 1 | |||
| E | 7 | 5 | 1 | — | 3 | |
| F | 3 | — |
Решение по шагам
4 шагаИз пункта A есть дорога только в пункт B, поэтому любой путь из A начинается с участка A–B длиной 4.
$$L_{A B} = 4$$Из B можно попасть в D, а затем в E и F. Длина маршрута A–B–D–E–F равна:
$$4 + 5 + 1 + 3 = 13$$Другие доступные маршруты длиннее: например, A–B–E–F имеет длину $4 + 7 + 3 = 14$, а маршрут через C — $4 + 7 + 5 + 3 = 19$.
Следовательно, кратчайший путь имеет длину 13.
Где здесь ошибаются
Складывают длины дорог маршрута A–B–E–F и получают 14, не проверяя путь через D.
Используют отсутствующую в таблице прямую дорогу.
Забывают включить в сумму длину участка E–F.