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