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