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

Решение:

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

Начальная точка: А. Расстояние до А = 0.

Расстояния до других вершин:

• d(A) = 0
• d(B) = ∞
• d(C) = ∞
• d(D) = ∞
• d(E) = ∞
• d(F) = ∞

Шаг 1: Посещаем А (расстояние 0).

• d(B) = min(∞, d(A) + AB) = min(∞, 0 + 2) = 2
• d(C) = min(∞, d(A) + AC) = min(∞, 0 + 1) = 1

Посещённые: {A}. Непосещённые: {B(2), C(1), D(∞), E(∞), F(∞)}.

Шаг 2: Выбираем ближайшую непосещённую вершину – C (расстояние 1).

• d(B) = min(2, d(C) + CB) = min(2, 1 + 1) = 2
• d(D) = min(∞, d(C) + CD) = min(∞, 1 + 2) = 3
• d(E) = min(∞, d(C) + CE) = min(∞, 1 + 1) = 2

Посещённые: {A, C}. Непосещённые: {B(2), D(3), E(2), F(∞)}.

Шаг 3: Выбираем ближайшую непосещённую вершину – B или E (расстояние 2). Выберем B.

• d(D) = min(3, d(B) + BD) = min(3, 2 + 1) = 3
• d(E) = min(2, d(B) + BE) = min(2, 2 + 3) = 2

Посещённые: {A, C, B}. Непосещённые: {D(3), E(2), F(∞)}.

Шаг 4: Выбираем ближайшую непосещённую вершину – E (расстояние 2).

• d(D) = min(3, d(E) + ED) = min(3, 2 + 1) = 3
• d(F) = min(∞, d(E) + EF) = min(∞, 2 + 5) = 7

Посещённые: {A, C, B, E}. Непосещённые: {D(3), F(7)}.

Шаг 5: Выбираем ближайшую непосещённую вершину – D (расстояние 3).

• d(F) = min(7, d(D) + DF) = min(7, 3 + 4) = 7

Посещённые: {A, C, B, E, D}. Непосещённые: {F(7)}.

Шаг 6: Выбираем ближайшую непосещённую вершину – F (расстояние 7).

Ответ: 7