4. Ребята решили попробовать себя в картографии и нарисовали вот такую схему населенных пунктов. Буквами указаны названия населенных пунктов, а в таблице дано время пути по соответствующей дороге в минутах. Определите, за какое минимальное время можно добраться из населенного пункта А в пункт F в минутах.

Задание 4. Минимальное время пути

Разбор:

Чтобы найти минимальное время пути из пункта А в пункт F, будем использовать алгоритм Дейкстры.

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

Шаг 1: Инициализация.

• Расстояния до всех вершин: A=0, B=∞, C=∞, D=∞, E=∞, F=∞.
• Посещенные вершины: пусто.
• Очередь: {A:0}

Шаг 2: Обрабатываем вершину A.

• Текущая вершина: A (расстояние 0).
• Соседи A: B (12).
• Обновляем расстояние до B: 0 + 12 = 12.
• Очередь: {B:12}
• Посещенные: {A}

Шаг 3: Обрабатываем вершину B.

• Текущая вершина: B (расстояние 12).
• Соседи B: A (12), C (13), D (9), E (7).
• Обновляем расстояния:
• C: 12 + 13 = 25. Очередь: {C:25}
• D: 12 + 9 = 21. Очередь: {D:21}
• E: 12 + 7 = 19. Очередь: {E:19}
• Очередь: {C:25, D:21, E:19}
• Посещенные: {A, B}

Шаг 4: Обрабатываем вершину E.

• Текущая вершина: E (расстояние 19).
• Соседи E: B (7), D (4).
• Обновляем расстояния:
• D: 19 + 4 = 23. Текущее расстояние до D = 21. Не обновляем.
• Очередь: {C:25, D:21}
• Посещенные: {A, B, E}

Шаг 5: Обрабатываем вершину D.

• Текущая вершина: D (расстояние 21).
• Соседи D: B (9), C (3), F (7).
• Обновляем расстояния:
• C: 21 + 3 = 24. Текущее расстояние до C = 25. Обновляем: C=24.
• F: 21 + 7 = 28. Очередь: {F:28}
• Очередь: {C:24, F:28}
• Посещенные: {A, B, E, D}

Шаг 6: Обрабатываем вершину C.

• Текущая вершина: C (расстояние 24).
• Соседи C: B (13), F (2).
• Обновляем расстояния:
• F: 24 + 2 = 26. Текущее расстояние до F = 28. Обновляем: F=26.
• Очередь: {F:26}
• Посещенные: {A, B, E, D, C}

Шаг 7: Обрабатываем вершину F.

• Текущая вершина: F (расстояние 26).
• Соседи F: C (2), D (7).
• Расстояния до соседей не обновляются, так как F уже является конечной вершиной.
• Посещенные: {A, B, E, D, C, F}

Минимальное время из А в F составляет 26 минут.

Ответ: 26