Пример решения задачи нахождения кратчайшего пути

В простом взвешенном графе на рисунке 7.3.1 найти кратчайший путь из в , используя алгоритм Дейкстры.

x₂ 3 x₄ 6 x₇

6 6 7 5

x₀ 4 x₁ 9 x₈

3 x₅ 4 11

8 10

x₃ 7 x₆

Рисунок 4.5 - Простой взвешенный граф

Табли­ца 4.3 - Последо­вательное изменение меток вершин

	Метки
X0
X1
X2
X3
X4
X5
X6
X7
X8

Таблица 4.4 - Последо­вательное изменение меток

	Метки
X1
X2
X3
X4
X5
X6
X7
X8

Из таблиц 4.3 и 4.4 можно определить кратчайший путь и его длину.

Длину кратчайшего пути в таблице 4.3 определяем по постоянной метке, которую имеет конечная вершина: вершина имеет постоянную метку равную 20, значит длина кратчайшего пути l ()=20.

Сам кратчайший путь определяем из таблицы 4.4: метка последней вершины указывает на индекс вершины предшествующей ей и т.д. пока не дойдем до начальной вершины. Вершины в обратном порядке указывают кратчайший путь: .

l=6 l=9 l=15

x₂ 3 x₄ 6 x₇

6 6 7 5

x₀ 4 x₁ 9 x₈

3 l=4 x₅ l=13 4 11 l=20

8 10

x₃ 7 x₆

l=7 l=14

Рисунок 4.6 - Окончательное распределение меток и кратчайший путь

Дата добавления: 2014-01-06