Выбор кратчайших путей (маршрутизация) в сетях.

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

Обозначим через D(v) расстояние от источника 1 до узла v. Пусть L(i, j) - заданная стоимость пути между узлами i и j. Алгоритм состоит из двух частей: начального шага и итераций, повторяющихся до завершения алгоритма. В множество N будем заносить кратчайшие пути к узлам.

1. Начальный шаг

Устанавливаем N = {1}. Для каждого узла v, не принадлежащего множеству N, устанавливаем D(v) = L(1,v). (Расстояние до узлов, не соединенных с узлом 1, принимаем равным бесконечности).

2. Каждый последующий шаг.

Находим не принадлежащий множеству N узел w, для которого D(w) минимально и включаем w в множество N. Затем обновляем значения D(w) для всех остальных узлов, не принадлежащих N путем вычисления

D(v) min[D(v), D(w)+L(w,v)]/

Шаг 2 повторяется, пока в множество N не войдут все узлы