Ответ:
Ищем для каждой пары пунктов маршрут с наименьшей суммарной длиной. Если прямой дороги недостаточно, сравниваем её длину с длинами маршрутов через промежуточные пункты.
| Пункт | A | B | C | D | E |
|---|---|---|---|---|---|
| A | 0 | 2 | 5 | 4 | 7 |
| B | 2 | 0 | 3 | 6 | 5 |
| C | 5 | 3 | 0 | 6 | 8 |
| D | 4 | 6 | 6 | 0 | 8 |
| E | 7 | 5 | 8 | 8 | 0 |
Например, кратчайший путь из A в C проходит через B: 2 + 3 = 5. Кратчайший путь из A в E проходит через B: 2 + 5 = 7.
Ответ: таблица кратчайших расстояний заполнена значениями, указанными выше.
