Ответ:
📍Тапни предложение — включится подсветка для легкого переноса текста в тетрадь.
По таблице дороги имеют длины: AC = 8 км, AD = 10 км, BD = 4 км, BE = 1 км, CD = 1 км, CE = 3 км. Длины одинаковы в обоих направлениях.
Сравним прямые дороги с маршрутами через промежуточные пункты:
- A–D: через C получается 8 + 1 = 9 км, что короче прямой дороги длиной 10 км.
- A–B: кратчайший найденный маршрут A–C–D–B равен 8 + 1 + 4 = 13 км.
- A–E: маршрут A–C–E равен 8 + 3 = 11 км.
- B–C: маршрут B–D–C равен 4 + 1 = 5 км.
- D–E: маршрут D–C–E равен 1 + 3 = 4 км.
Итоговые длины кратчайших путей:
| Пункты | A | B | C | D | E |
|---|---|---|---|---|---|
| A | 0 | 13 | 8 | 9 | 11 |
| B | 13 | 0 | 5 | 4 | 1 |
| C | 8 | 5 | 0 | 1 | 3 |
| D | 9 | 4 | 1 | 0 | 4 |
| E | 11 | 1 | 3 | 4 | 0 |
Числа в таблице — километры; на главной диагонали указано расстояние от пункта до самого себя.
По таблице дороги имеют длины: AC = 8 км, AD = 10 км, BD = 4 км, BE = 1 км, CD = 1 км, CE = 3 км. Длины одинаковы в обоих направлениях.
Сравним прямые дороги с маршрутами через промежуточные пункты:
- A–D: через C получается 8 + 1 = 9 км, что короче прямой дороги длиной 10 км.
- A–B: кратчайший найденный маршрут A–C–D–B равен 8 + 1 + 4 = 13 км.
- A–E: маршрут A–C–E равен 8 + 3 = 11 км.
- B–C: маршрут B–D–C равен 4 + 1 = 5 км.
- D–E: маршрут D–C–E равен 1 + 3 = 4 км.
Итоговые длины кратчайших путей:
| Пункты | A | B | C | D | E |
|---|---|---|---|---|---|
| A | 0 | 13 | 8 | 9 | 11 |
| B | 13 | 0 | 5 | 4 | 1 |
| C | 8 | 5 | 0 | 1 | 3 |
| D | 9 | 4 | 1 | 0 | 4 |
| E | 11 | 1 | 3 | 4 | 0 |
Числа в таблице — километры; на главной диагонали указано расстояние от пункта до самого себя.
