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

Общие сведения

Дан ориентированный или неориентированный взвешенный граф; веса всех рёбер неотрицательны. Требуется определить кратчайшие расстояния из данной вершины до всех остальных.

Пусть изначально расстояние до стартовой вершины равно нулю, расстояния до всех остальных вершин — бесконечности. Определим ближайшую вершину (на первом шаге таковой будет стартовая вершина). Как будет показано ниже, расстояние до выбранной вершины является кратчайшим и в дальнейшем не изменяется, поэтому его можно использовать для пересчёта расстояний до соседних вершин.

Итак, пусть v — текущая ближайшая вершина и существует ребро v→u веса w. Обозначим кратчайшее расстояние до вершины v как dist[v], текущее расстояние до вершины u — dist[u]. Тогда если (dist[v] + w) < dist[u], то мы нашли более короткий путь к вершине u — он проходит через вершину v и ребро v→u. Соответственно, мы можем обновить значение dist[u]. Такое обновление называется релаксацией.

После проведения всех возможных релаксаций ближайшая вершина исключается из дальнейшего рассмотрения. Таким образом, на каждой итерации будет определяться кратчайшее расстояние до одной из вершин графа, и всего для решения задачи понадобится V итераций. Очевидно, что после выполнения алгоритма расстояния до недостижимых вершин останутся равными бесконечности.

Доказательство корректности алгоритма Дейкстры

Доказательство того факта, что на каждой итерации расстояние до обрабатываемой вершины действительно является кратчайшим, проводится по индукции. Для базового случая (обрабатывается стартовая вершина, расстояние до неё равно нулю) утверждение выполняется. Далее, пусть утверждение выполняется для всех обработанных вершин (значения dist[] для них рассчитаны верно), а на текущем шаге выбрана вершина v. Обозначим через u первую необработанную вершину на кратчайшем пути до v, через t — вершину, предшествующую u на этом пути. Кратчайшее расстояние до вершины u равно сумме dist[t] и веса ребра t→u; эта сумма уже была записана в dist[u] при проведении релаксаций из вершины t, следовательно, значение dist[u] действительно равно кратчайшему расстоянию до вершины u. Далее, заметим, что должны выполняться условия dist[v] ≤ dist[u] (так как вершина v является ближайшей на текущем шаге) и dist[v] ≥ dist[u] (так как u лежит на пути до v, а граф не содержит рёбер отрицательного веса). Отсюда dist[v] = dist[u], то есть в момент выбора вершины v значение dist[v] действительно равно кратчайшему расстоянию до неё.

Демонстрация работы

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

Реализация для плотных графов

Здесь и далее будем считать, что граф задан списками смежности, а количество вершин равно N.

const int N = 1000;
  
struct Edge {
    int vFrom, vTo;
    int weight;
};
vector<Edge> g[N];

Алгоритм принимает индекс стартовой вершины vStart и заполняет глобальный массив dist[]. Роль значения «бесконечность« выполняет достаточно большая константа INF; её значение должно быть больше максимального возможного расстояния между вершинами, но не допускать переполнения при проведении релаксаций (для избежания переполнений также можно ввести в основной цикл контрольное условие: если расстояние до ближайшей вершины равно INF, выполнение алгоритма завершается). Логический массив used[] предназначен для отметки обработанных вершин.

После начальной инициализации used[] и dist[] производится N итераций алгоритма, на каждой из которых сначала определяется ближайшая из необработанных вершин (используется наивный поиск минимума с асимптотикой O(V)), затем выбранная вершина помечается как обработанная и производится попытка релаксации для каждого исходящего из неё ребра.

Хотя на каждой итерации выполняется различное число попыток релаксации, общее их количество равно E, так как будет просмотрено каждое ребро (один раз, если рёбра направленные, дважды — если ненаправленные). Таким образом, общая асимптотическая оценка алгоритма равна O(V² + E).

const int INF = 1 << 30;
int dist[N];
bool used[N];

void dijkstra(int vStart) {
    for (int i = 0; i < N; i++) {
        used[i] = false;
        dist[i] = INF;
    }
    dist[vStart] = 0;
    
    for (int i = 0; i < N; i++) {
        int v = -1;
        for (int j = 0; j < N; j++)
            if (!used[j] && (v == -1 || dist[j] < dist[v]))
                v = j;
        used[v] = true;
        for (int j = 0; j < g[v].size(); j++) {
            int u = g[v][j].vTo;
            int w = g[v][j].weight;
            if (dist[u] > dist[v] + w)
                dist[u] = dist[v] + w;
        }              
    }
}

Реализация для разреженных графов

Алгоритм Дейкстры выполняет O(V) поисков ближайшей вершины и O(E) релаксаций. В предыдущей реализации информация о расстоянии до вершин хранилась в массиве, что позволяло производить операции первого типа за O(V), второго типа — за O(1). Итоговая оценка O(V² + E) является неудовлетворительной для разреженных графов (в которых E << V²). Поэтому в данном случае имеет смысл использовать структуры данных, позволяющие производить и поиск минимума, и обновление элементов с асимптотикой O(logV).

Одной из таких структур является сбалансированное двоичное дерево поиска, представленное в STL контейнером set. Так как требуется упорядочить вершины согласно расстоянию до них, будем хранить множество s из пар (расстояние, индекс вершины). Пары STL сравниваются начиная с первого поля, что обеспечит нужный порядок. Множество s также будет выполнять функции массива used[], так как в него будут помещаться только необработанные вершины.

Теперь для определения ближайшей вершины достаточно обратиться к полю s.begin(). При проведении релаксации нужно предварительно удалить из множества пару со старым расстоянием (если она там была), а затем добавить пару с обновлённым расстоянием.

Итоговая асимптотика данной реализации составляет O((V + E)logV). Следует обратить внимание на то, что для плотных графов (в которых E ~ V²) эта реализация оказывается медленнее предыдущей.

const int INF = 1 << 30;
int dist[N];
set< pair<int, int> > s;

void dijkstra(int vStart) {
    for (int i = 0; i < N; i++)
        dist[i] = INF;
    dist[vStart] = 0;
    s.insert(make_pair(dist[vStart], vStart));
    
    while (!s.empty()) {
        int v = s.begin()->second;
        s.erase(s.begin());
        for (int j = 0; j < g[v].size(); j++) {
            int u = g[v][j].vTo;
            int w = g[v][j].weight;
            if (dist[u] > dist[v] + w) {
                s.erase(make_pair(dist[u], u));
                dist[u] = dist[v] + w;
                s.insert(make_pair(dist[u], u));
            }
        }              
    }
}