4. Между населёнными пунктами А, В, С, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами А и Е. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.

Решение:

Используем алгоритм Дейкстры для нахождения кратчайшего пути от пункта А до пункта Е.

Таблица расстояний:

Шаги алгоритма:

1. Старт: Находимся в А. Расстояние до А = 0. Доступны: B (3), C (5), D (15).
2. Выбираем ближайший: B (3). Расстояние до B = 3. Из B доступны: A (3 - уже посещен), E (2). Новое расстояние до E через B = 3 + 2 = 5.
3. Выбираем ближайший: C (5). Расстояние до C = 5. Из C доступны: A (5 - посещен), D (3). Новое расстояние до D через C = 5 + 3 = 8.
4. Выбираем ближайший: D. Текущее расстояние до D = 15. Через C расстояние = 8. Обновляем: D = 8. Из D доступны: C (3 - посещен), E (7). Новое расстояние до E через D = 8 + 7 = 15.
5. Выбираем ближайший: E. Текущее расстояние до E = 5. Через D расстояние = 15. Оставляем 5.

Наименьшее расстояние до E — 5.

Путь: A → B → E.

Ответ: Длина кратчайшего пути между пунктами А и Е составляет 5 километров.