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

Краткое пояснение:

Пошаговое решение:

Представим дороги как граф, где пункты — это вершины, а дороги — ребра с весами, равными их протяженности.

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

• Начальный узел: B. Устанавливаем расстояние до B как 0, до всех остальных — бесконечность.
• Посещенные узлы: {}.
• Непосещенные узлы: {A, B, C, D, E, F}.
• Таблица расстояний: B=0, A=∞, C=∞, D=∞, E=∞, F=∞.

Шаг 2: Выбор узла с минимальным расстоянием из непосещенных.

• Выбираем B (расстояние 0). Добавляем B в посещенные узлы.
• Непосещенные узлы: {A, C, D, E, F}.
• Обновляем расстояния до соседей B:
• B → A: расстояние 5 (через B). Таблица: B=0, A=5, C=∞, D=∞, E=∞, F=∞.
• B → C: расстояние 2 (через B). Таблица: B=0, A=5, C=2, D=∞, E=∞, F=∞.
• B → F: расстояние 3 (через B). Таблица: B=0, A=5, C=2, D=∞, E=∞, F=3.

Шаг 3: Выбор узла с минимальным расстоянием из непосещенных.

• Выбираем C (расстояние 2). Добавляем C в посещенные узлы.
• Непосещенные узлы: {A, D, E, F}.
• Обновляем расстояния до соседей C:
• C → A: расстояние 2 (через C). Итоговое расстояние до A: min(5, 2+2) = 4. Таблица: B=0, A=4, C=2, D=∞, E=∞, F=3.
• C → D: расстояние 2 (через C). Таблица: B=0, A=4, C=2, D=2, E=∞, F=3.

Шаг 4: Выбор узла с минимальным расстоянием из непосещенных.

• Выбираем D (расстояние 2). Добавляем D в посещенные узлы.
• Непосещенные узлы: {A, E, F}.
• Обновляем расстояния до соседей D:
• D → A: расстояние 4 (через D). Итоговое расстояние до A: min(4, 2+4) = 4. Таблица: B=0, A=4, C=2, D=2, E=∞, F=3.
• D → E: расстояние 3 (через D). Таблица: B=0, A=4, C=2, D=2, E=3, F=3.
• D → F: расстояние 2 (через D). Итоговое расстояние до F: min(3, 2+2) = 3. Таблица: B=0, A=4, C=2, D=2, E=3, F=3.

Шаг 5: Выбор узла с минимальным расстоянием из непосещенных.

• Выбираем E (расстояние 3). Добавляем E в посещенные узлы.
• Непосещенные узлы: {A, F}.
• Обновляем расстояния до соседей E:
• E → A: расстояние 3 (через E). Итоговое расстояние до A: min(4, 3+3) = 4. Таблица: B=0, A=4, C=2, D=2, E=3, F=3.
• E → F: расстояние 5 (через E). Итоговое расстояние до F: min(3, 3+5) = 3. Таблица: B=0, A=4, C=2, D=2, E=3, F=3.

Шаг 6: Выбор узла с минимальным расстоянием из непосещенных.

• Выбираем F (расстояние 3). Добавляем F в посещенные узлы.
• Непосещенные узлы: {A}.
• Обновляем расстояния до соседей F:
• F → A: расстояние 7 (через F). Итоговое расстояние до A: min(4, 3+7) = 4. Таблица: B=0, A=4, C=2, D=2, E=3, F=3.

Шаг 7: Выбор узла с минимальным расстоянием из непосещенных.

• Выбираем A (расстояние 4). Добавляем A в посещенные узлы.
• Непосещенные узлы: {}.

Шаг 8: Определение кратчайшего пути до D.

• Кратчайшее расстояние до D равно 2 (путь B → C → D).

Ответ: 2