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

Данный алгоритм находит самый короткий путь от данного узла до всех других узлов, работает следующим образом.

1. Маркируйте все узлы, кроме стартового, парой значений, состоящей из расстояния до данного узла (первоначально « ») и именем узла подхода (первоначально «-»). Узел подхода – это ближайший (слева) соседний узел, к которому осуществляется непосредственный подход через маркируемый узел.

2. Начиная со стартового узла, выберите узел с самым низким совокупным весом; считайте этот узел установленным (или фиксированным).

3. Маркируйте соседние с установленным узлы совокупным расстоянием от стартового узла и именем узла подхода.

4. Если узел уже маркирован, то его метка заменяется на новую, совокупное расстояние которой меньше, чем существующее совокупное расстояние.

5. Продолжайте маркировку, пока все узлы не будут установлены.

После фиксации всех узлов результирующий совокупный вес позволяет рассчитать самый короткий путь от исходного узла. Это можно сделать, считая в обратном порядке узлы подхода каждого узла на соответствующем пути. Рассмотрим пример действия по алгоритму Дейкстры более подробно.

1. К аждый узел кроме стартового первоначально маркируется как .

Рис. 16 Пример применения алгоритма Дейкстры, шаг первый

2. Н ачните с узла A, зафиксируйте его, перемаркируйте соседние (справа) узлы B и F с учетом их расстояний.

Рис. 17 Пример применения алгоритма Дейкстры, шаг второй

3. Т еперь самым малым весом обладает узел B, поэтому для него повторяются все действия пункта 2.

Рис. 18 Пример применения алгоритма Дейкстры, шаг третий

4. Теперь узел G имеет самый малый вес, поэтому он и используется. Новый вес для F меньше чем существующий, поэтому старая метка (6,A) заменяется новой (5,G). То же самое происходит и с узлом C.

Р ис. 19 Пример применения алгоритма Дейкстры, шаг четвертый

5. П овторите предыдущую процедуру для узла F. В результате узел E должен был бы получить метку (9, F), но его существующая метка (6,G) имеет более низкий суммарный вес до исходного узла, так что оставлена без изменений.

Рис. 20 Пример применения алгоритма Дейкстры, шаг пятый

6. П овторите процедуру для узла C.

Рис. 21 Пример применения алгоритма Дейкстры, шаг шестой

6. Повторите процедуру для узла E. В результате метка узла D (9,C) будет заменена на (8,E).

Р ис. 22 Пример применения алгоритма Дейкстры, шаг седьмой

Установка узла D завершает процедуру алгоритма Дейкстры. Нетрудно видеть, что самый короткий путь от A до D имеет совокупный вес 8, и читая метки, начинающиеся с узда D, в обратном порядке, получаем наикратчайший маршрут: D E G B A.