Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице слева. Определи длину кратчайшего пути между пунктами A и B, проходящего через пункт C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 2 | 8 | 4 | 1 | |
| B | 2 | 2 | 7 | 5 | |
| C | 8 | 2 | 4 | 6 | |
| D | 4 | 7 | 4 | 2 | |
| E | 1 | 5 | 6 | 2 |
Путь состоит из двух частей: от A до C и от C до B. Пункт B в первой части повторно не посещаем.
Участок C–B: прямая дорога,
Участок A–C, не заходя в B:
- A–C:
- A–D–C:
- A–E–C:
- A–E–D–C:
Наименьшая длина A–C равна
Всего:
Кратчайший путь через заданный пункт — это кратчайший путь до этого пункта плюс кратчайший путь от него до конца.
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице слева. Определи длину кратчайшего пути между пунктами A и D, проходящего через пункт E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 1 | 7 | 3 | 5 | |
| B | 1 | 4 | 1 | ||
| C | 7 | 5 | 1 | ||
| D | 3 | 1 | 5 | 3 | |
| E | 5 | 1 | 3 |
Путь делим на участки A→E и E→D. Пункт D в первой части не посещаем.
Участок A–E:
- A–E:
- A–B–C–E:
- A–C–E:
Наименьшая длина A–E равна
Участок E–D:
- E–D:
- E–C–D:
Наименьшая длина E–D равна
Всего:
Сначала находим кратчайший путь до промежуточного пункта E, затем от E до конечного пункта D, и складываем.
