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

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

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

Пошаговое решение (алгоритм Дейкстры):

1. Инициализация: Расстояния до вершин: A=0, B=∞, C=∞, D=∞, E=∞, F=∞. Посещенные вершины: {}.
2. Шаг 1 (Вершина A):
   - Расстояние до A = 0. Посещенные: {A}.
   - Обновляем соседей A: B (3), C (5), D (1), F (15).
   - Текущие расстояния: A=0, B=3, C=5, D=1, E=∞, F=15.
3. Шаг 2 (Вершина D):
   - Следующая ближайшая непосещенная вершина - D (расстояние 1). Посещенные: {A, D}.
   - Обновляем соседей D: C (1+1=2), E (1+2=3), F (1+6=7).
   - Текущие расстояния: A=0, B=3, C=min(5, 2)=2, D=1, E=3, F=min(15, 7)=7.
4. Шаг 3 (Вершина C):
   - Следующая ближайшая непосещенная вершина - C (расстояние 2). Посещенные: {A, D, C}.
   - Обновляем соседей C: B (2+1=3), D (2+1=3, но D уже посещена с меньшим расстоянием).
   - Текущие расстояния: A=0, B=min(3, 3)=3, C=2, D=1, E=3, F=7.
5. Шаг 4 (Вершина B):
   - Следующая ближайшая непосещенная вершина - B (расстояние 3). Посещенные: {A, D, C, B}.
   - Обновляем соседей B: A (3+3=6, A посещена), C (3+1=4, C посещена с меньшим расстоянием).
   - Текущие расстояния: A=0, B=3, C=2, D=1, E=3, F=7.
6. Шаг 5 (Вершина E):
   - Следующая ближайшая непосещенная вершина - E (расстояние 3). Посещенные: {A, D, C, B, E}.
   - Обновляем соседей E: D (3+2=5, D посещена), F (3+2=5).
   - Текущие расстояния: A=0, B=3, C=2, D=1, E=3, F=min(7, 5)=5.
7. Шаг 6 (Вершина F):
   - Следующая ближайшая непосещенная вершина - F (расстояние 5). Посещенные: {A, D, C, B, E, F}.
   - Обновляем соседей F: D (5+6=11, D посещена), E (5+2=7, E посещена).
   - Конечные расстояния: A=0, B=3, C=2, D=1, E=3, F=5.

Ответ: 5