Решение задачи: Минимальный путь в орграфе алгоритмом Дейкстры

Решим задачу по нахождению минимального пути в орграфе из вершины \(s = v_1\) до вершины \(t = v_7\) с помощью алгоритма Дейкстры. Исходные данные представлены в виде матрицы смежности:

	\(v_1\)	\(v_2\)	\(v_3\)	\(v_4\)	\(v_5\)	\(v_6\)	\(v_7\)
\(v_1\)	-	5	\(\infty\)	10	8	12	\(\infty\)
\(v_2\)	\(\infty\)	-	7	\(\infty\)	4	9	\(\infty\)
\(v_3\)	\(\infty\)	\(\infty\)	-	\(\infty\)	\(\infty\)	6	11
\(v_4\)	\(\infty\)	\(\infty\)	\(\infty\)	-	\(\infty\)	\(\infty\)	14
\(v_5\)	\(\infty\)	\(\infty\)	6	\(\infty\)	-	13	21
\(v_6\)	\(\infty\)	\(\infty\)	\(\infty\)	8	\(\infty\)	-	9
\(v_7\)	\(\infty\)	\(\infty\)	\(\infty\)	\(\infty\)	\(\infty\)	\(\infty\)	-

Обозначим \(D[v]\) как текущую минимальную длину пути от \(v_1\) до вершины \(v\). Изначально: \(D[v_1] = 0\) \(D[v_i] = \infty\) для всех \(i \neq 1\) Множество посещенных вершин \(S = \emptyset\). Шаг 1. Выбираем вершину с минимальным \(D\) из непосещенных. Это \(v_1\). \(D[v_1] = 0\). Добавляем \(v_1\) в \(S\). Обновляем расстояния для соседей \(v_1\): \(D[v_2] = \min(\infty, D[v_1] + \text{вес}(v_1, v_2)) = \min(\infty, 0 + 5) = 5\). Путь: \(v_1 \to v_2\). \(D[v_4] = \min(\infty, D[v_1] + \text{вес}(v_1, v_4)) = \min(\infty, 0 + 10) = 10\). Путь: \(v_1 \to v_4\). \(D[v_5] = \min(\infty, D[v_1] + \text{вес}(v_1, v_5)) = \min(\infty, 0 + 8) = 8\). Путь: \(v_1 \to v_5\). \(D[v_6] = \min(\infty, D[v_1] + \text{вес}(v_1, v_6)) = \min(\infty, 0 + 12) = 12\). Путь: \(v_1 \to v_6\). Текущие расстояния: \(D[v_1] = 0\) (посещена) \(D[v_2] = 5\) (путь \(v_1 \to v_2\)) \(D[v_3] = \infty\) \(D[v_4] = 10\) (путь \(v_1 \to v_4\)) \(D[v_5] = 8\) (путь \(v_1 \to v_5\)) \(D[v_6] = 12\) (путь \(v_1 \to v_6\)) \(D[v_7] = \infty\) Шаг 2. Выбираем вершину с минимальным \(D\) из непосещенных. Это \(v_2\) с \(D[v_2] = 5\). Добавляем \(v_2\) в \(S\). Обновляем расстояния для соседей \(v_2\): \(D[v_3] = \min(\infty, D[v_2] + \text{вес}(v_2, v_3)) = \min(\infty, 5 + 7) = 12\). Путь: \(v_1 \to v_2 \to v_3\). \(D[v_5] = \min(8, D[v_2] + \text{вес}(v_2, v_5)) = \min(8, 5 + 4) = \min(8, 9) = 8\). Путь: \(v_1 \to v_5\) (путь через \(v_2\) длиннее). \(D[v_6] = \min(12, D[v_2] + \text{вес}(v_2, v_6)) = \min(12, 5 + 9) = \min(12, 14) = 12\). Путь: \(v_1 \to v_6\) (путь через \(v_2\) длиннее). Текущие расстояния: \(D[v_1] = 0\) (посещена) \(D[v_2] = 5\) (посещена) \(D[v_3] = 12\) (путь \(v_1 \to v_2 \to v_3\)) \(D[v_4] = 10\) (путь \(v_1 \to v_4\)) \(D[v_5] = 8\) (путь \(v_1 \to v_5\)) \(D[v_6] = 12\) (путь \(v_1 \to v_6\)) \(D[v_7] = \infty\) Шаг 3. Выбираем вершину с минимальным \(D\) из непосещенных. Это \(v_5\) с \(D[v_5] = 8\). Добавляем \(v_5\) в \(S\). Обновляем расстояния для соседей \(v_5\): \(D[v_3] = \min(12, D[v_5] + \text{вес}(v_5, v_3)) = \min(12, 8 + 6) = \min(12, 14) = 12\). Путь: \(v_1 \to v_2 \to v_3\) (путь через \(v_5\) длиннее). \(D[v_6] = \min(12, D[v_5] + \text{вес}(v_5, v_6)) = \min(12, 8 + 13) = \min(12, 21) = 12\). Путь: \(v_1 \to v_6\) (путь через \(v_5\) длиннее). \(D[v_7] = \min(\infty, D[v_5] + \text{вес}(v_5, v_7)) = \min(\infty, 8 + 21) = 29\). Путь: \(v_1 \to v_5 \to v_7\). Текущие расстояния: \(D[v_1] = 0\) (посещена) \(D[v_2] = 5\) (посещена) \(D[v_3] = 12\) (путь \(v_1 \to v_2 \to v_3\)) \(D[v_4] = 10\) (путь \(v_1 \to v_4\)) \(D[v_5] = 8\) (посещена) \(D[v_6] = 12\) (путь \(v_1 \to v_6\)) \(D[v_7] = 29\) (путь \(v_1 \to v_5 \to v_7\)) Шаг 4. Выбираем вершину с минимальным \(D\) из непосещенных. Это \(v_4\) с \(D[v_4] = 10\). Добавляем \(v_4\) в \(S\). Обновляем расстояния для соседей \(v_4\): \(D[v_7] = \min(29, D[v_4] + \text{вес}(v_4, v_7)) = \min(29, 10 + 14) = \min(29, 24) = 24\). Путь: \(v_1 \to v_4 \to v_7\). Текущие расстояния: \(D[v_1] = 0\) (посещена) \(D[v_2] = 5\) (посещена) \(D[v_3] = 12\) (путь \(v_1 \to v_2 \to v_3\)) \(D[v_4] = 10\) (посещена) \(D[v_5] = 8\) (посещена) \(D[v_6] = 12\) (путь \(v_1 \to v_6\)) \(D[v_7] = 24\) (путь \(v_1 \to v_4 \to v_7\)) Шаг 5. Выбираем вершину с минимальным \(D\) из непосещенных. Это \(v_3\) с \(D[v_3] = 12\) или \(v_6\) с \(D[v_6] = 12\). Выберем \(v_3\). Добавляем \(v_3\) в \(S\). Обновляем расстояния для соседей \(v_3\): \(D[v_6] = \min(12, D[v_3] + \text{вес}(v_3, v_6)) = \min(12, 12 + 6) = \min(12, 18) = 12\). Путь: \(v_1 \to v_6\) (путь через \(v_3\) длиннее). \(D[v_7] = \min(24, D[v_3] + \text{вес}(v_3, v_7)) = \min(24, 12 + 11) = \min(24, 23) = 23\). Путь: \(v_1 \to v_2 \to v_3 \to v_7\). Текущие расстояния: \(D[v_1] = 0\) (посещена) \(D[v_2] = 5\) (посещена) \(D[v_3] = 12\) (посещена) \(D[v_4] = 10\) (посещена) \(D[v_5] = 8\) (посещена) \(D[v_6] = 12\) (путь \(v_1 \to v_6\)) \(D[v_7] = 23\) (путь \(v_1 \to v_2 \to v_3 \to v_7\)) Шаг 6. Выбираем вершину с минимальным \(D\) из непосещенных. Это \(v_6\) с \(D[v_6] = 12\). Добавляем \(v_6\) в \(S\). Обновляем расстояния для соседей \(v_6\): \(D[v_4]\) - нет ребра из \(v_6\) в \(v_4\). \(D[v_7] = \min(23, D[v_6] + \text{вес}(v_6, v_7)) = \min(23, 12 + 9) = \min(23, 21) = 21\). Путь: \(v_1 \to v_6 \to v_7\). Текущие расстояния: \(D[v_1] = 0\) (посещена) \(D[v_2] = 5\) (посещена) \(D[v_3] = 12\) (посещена) \(D[v_4] = 10\) (посещена) \(D[v_5] = 8\) (посещена) \(D[v_6] = 12\) (посещена) \(D[v_7] = 21\) (путь \(v_1 \to v_6 \to v_7\)) Шаг 7. Выбираем вершину с минимальным \(D\) из непосещенных. Это \(v_7\) с \(D[v_7] = 21\). Добавляем \(v_7\) в \(S\). Все вершины посещены. Окончательный минимальный путь до \(v_7\) равен 21. Восстановим путь: \(v_7\) была достигнута из \(v_6\) (поскольку \(D[v_6] + \text{вес}(v_6, v_7) = 12 + 9 = 21\)). \(v_6\) была достигнута из \(v_1\) (поскольку \(D[v_1] + \text{вес}(v_1, v_6) = 0 + 12 = 12\)). Таким образом, минимальный путь: \(v_1 \to v_6 \to v_7\). Длина минимального пути: 21. Ответ: Минимальный путь из \(s = v_1\) до вершины \(t = v_7\) равен 21. Путь: \(v_1 \to v_6 \to v_7\).