Алгоритм Дейкстры — нахождения кратчайшего пути

Алгоритм Дейкстры (нахождение кратчайшего расстояния между вершинами графа)

В качестве примера решения алгоритма Дейкстры

Пусть дан граф 

Граф

Необходимо найти кратчайший путь из вершины A в вершину G

Решение

Приведём его к виду

Алгоритм Дейкстры граф

Инициализация графа

Начальной вершине графа присвоим значение 0, A=0

Оставшимся вершинам присваиваем значение с большим числом, пусть в данном случае будет 1000 (∞).

Шаг 1

Соседними вершинами A являются вершины C и B. Сначала посещаем вершину с минимальным путем – вершину C и помечаем её как текущую метку, затем по убыванию остальные вершины, в данном случае вершину B. Вершину A помечаем как посещённую.

Алгоритм Дейкстры - шаг 1

Шаг 2

Соседними вершинами С являются вершины B,D и E.  Посещаем вершину с наименьшем путем – вершину B и помечаем её как текущую метку, затем оставшиеся вершины — вершину D и E. Вершину С помечаем как посещённую.

Алгоритм Дейкстры - шаг 2

Шаг 3

Соседними вершинами B — вершина D и E.  Посещаем вершину с наименьшем путем – вершину D и помечаем её как текущую метку, затем вершину E. Вершину B помечаем как посещённую.

Алгоритм Дейкстры - шаг 3

Шаг 4

Соседние вершины D — вершина G и E.  Посещаем вершину с наименьшем путем – вершину E и помечаем её как текущую метку, затем вершину G. Вершину D помечаем как посещённую.

Алгоритм Дейкстры - шаг 4

Шаг 5

Соседней вершиной E является оставшиеся последняя вершина G.  Посещаем вершину G и помечаем как посещённую. На этом алгоритм заканчивается.

Алгоритм Дейкстры - шаг 5

Итак, самый короткий маршрут получился A C B D E G и равен 10.

короткий маршрут на графе

Таким образом, оптимальный путь алгоритм Дейкстры определяется выражением

if d[v]>d[u]+s[u,v] then d[v]=d[u]+s[u,v]

Leave a Reply

Ваш e-mail не будет опубликован.