5. Между населёнными пунктами А, В, С, D, E, F построены дороги, протяжённость которых приведена в таблице: A | B | C | D | E | F A | | 2 | 5 | | 9 B | 2 | | 2 | 1 | 5 C | 5 | 2 | | | 1 D | | 2 | | | 1 E | | | | | 1 F | 9 | 5 | 1 | 1 | Определите длину кратчайшего пути между пунктами А и F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

Задание 5. Кратчайший путь

Будем искать кратчайший путь от А до F, используя таблицу с расстояниями:

1. Путь 1: А → F. Прямая дорога: 9.
2. Путь 2: А → B → F. Расстояние: 2 + 5 = 7.
3. Путь 3: А → C → F. Расстояние: 5 + 1 = 6.
4. Путь 4: А → B → C → F. Расстояние: 2 + 2 + 1 = 5.
5. Путь 5: А → B → D → F. Расстояние: 2 + 1 + 1 = 4.
6. Путь 6: А → C → D → F. Расстояние: 5 + 2 + 1 = 8.
7. Путь 7: А → C → E → F. Расстояние: 5 + 1 + 1 = 7.

Сравнивая все возможные пути, видим, что самый короткий путь — это А → B → D → F, его длина равна 4.

Ответ: 4