Условие:
4. Между населенными пунктами А, В, С, D, E, F построены дороги, протяженность которых в (километрах) приведена в таблице.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 3 | 5 | 15 | |||
| B | 3 | 1 | 4 | |||
| C | 5 | 1 | 2 | 9 | ||
| D | 4 | 2 | 3 | 6 | ||
| E | 3 | 2 | ||||
| F | 15 | 9 | 6 | 2 |
Определите длину кратчайшего пути между пунктами А и F, проходящего через пункт С. Передвигаться можно только по дорогам, протяженность которых указана в таблице.
Решение:
Шаг 1. Из условия требуется найти кратчайший путь из пункта A в пункт F, при условии что маршрут должен обязательно проходить через пункт C. Шаг 2. Найдём кратчайший путь от A до C. Вариант 1: прямой путь A → C = 5 км. Вариант 2: путь через пункт B: A → B = 3 км, B → C = 1 к...