Вычисление кратчайшего пути в графе. Алгоритм Дейкстры
Алгоритм Дейкстры позволяет вычислить кратчайшие пути в графе с использованием весов ребер как меры расстояния. Может оказаться, что путь с наименьшим числом ребер не является путем с наименьшим весом. Алгоритм предусматривает определение набора узлов, S, для которых еще не были вычислены минимальное расстояние и следующий участок маршрута. В этом наборе инициализируются все узлы, кроме источника.
Затем алгоритм предусматривает применение цикла. При каждом проходе по циклу алгоритм выбирает и удаляет из набора S узел, который имеет наименьшее расстояние от источника. Удаляя узел u , алгоритм проверяет текущее расстояние от источника до каждого узла, смежного с узлом u, остающегося в наборе. Если путь от источника через узел u имеет меньший вес, чем текущий путь, алгоритм обновляет расстояние до смежного узла. После удаления из набора S всех узлов выполнение алгоритма заканчивается вычислением минимального расстояния до каждого узла и получением правильной таблицы маршрутизации с определением следующего участка маршрута для всех возможных путей.
Реализация алгоритма Дейкстры является несложной. Кроме структур данных, используемых для хранения информации о графе, алгоритм требует хранения трех структур данных: текущего расстояние к каждому узлу, следующего участка кратчайшего пути и информацию об оставшемся наборе узлов. Узлы могут быть пронумерованы от 1 до n. Благодаря этому в структуре данных можно использовать номера узлов в качестве индекса.
Алгоритм
Условные обозначения:
- А – начальная вершина
- D(u) – стоимость пути от источника до адресата, у которого на данный момент стоимость минимальна.
- Infiniti – значение, принимаемое в случае отсутствия такого ребра.
- S – все узлы кроме исходного
- C(u, v) – стоимость канала.
1.инициализация
{ D(A)=0;
Для всех узлов v{
Если(v смежный с А)
Тогда D(v)=C(A,v);
Иначе D(v)=?;}
2. цикл
Пока(S не пуст){
Выбрать u из S, чтобы D(u) было min;
Если (D(u) -> infinity) ошибка;
Удалить узел из набора S;
Для каждого v, для которого существует C(u, v){
Если узел v все еще находится в наборе S
C=D(u)+C(u, v);
Если С