Иллюстрация работы алгоритма Дикстры

Рисунок 4.2.11.2.1 Иллюстрация работы алгоритма Дикстры

Ниже дается формальное описание алгоритма. Сначала вводим некоторые определения.

Пусть D(v) равно сумме весов связей для данного пути.

Пусть c(i,j) равно весу связи между узлами с номерами i и j.

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

Устанавливаем множество узлов N = {1}.

Для каждого узла v не из множества n устанавливаем D(v)= c(1,v).

Для каждого шага находим узел w не из множества N, для которого D(w) минимально, и добавляем узел w в множество N.

Актуализируем D(v) для всех узлов не из множества N

D(v)=min{D(v), D(v)+c(w,v)}.

Повторяем шаги 2-4, пока все узлы не окажутся в множестве N.

Топология маршрутов для узла a приведена на нижней части Рисунок 4.2.11.2.1. В скобках записаны числа, характеризующие метрику отобранного маршрута согласно критерию пункта 3.

Содержание раздела