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