Алгоритм Дейкстры на C: список смежности, бинарная куча и кратчайшие пути

Алгоритм Дейкстры находит кратчайшие пути от одной вершины до всех остальных во взвешенном графе с неотрицательными рёбрами. Наивная реализация с линейным поиском минимума работает за O(n² + m), что приемлемо для плотных графов. Для разреженных графов, где m значительно меньше n², бинарная куча снижает сложность до O((n + m) log n).

Ниже — самодостаточная реализация на чистом C: список смежности в формате forward star, бинарная min-куча с ленивым удалением и восстановление пути через массив предшественников.

Представление графа: forward star​

Список смежности удобно хранить тремя параллельными массивами: to[], weight[], next_edge[] и массивом голов head[]. Каждое ребро получает индекс, а head[v] указывает на первое ребро, исходящее из вершины v. Следующее ребро того же источника находится через next_edge[]. Такой формат не требует динамических списков и экономит память.

#include <stdio.h>
#include <limits.h>

#define MAX_V 10000
#define MAX_E 100000
#define INF INT_MAX

int head[MAX_V];
int to[MAX_E];
int weight[MAX_E];
int next_edge[MAX_E];
int edge_count;

void init_graph(int n) {
    for (int i = 0; i < n; i++)
        head[i] = -1;
    edge_count = 0;
}

void add_edge(int u, int v, int w) {
    to[edge_count] = v;
    weight[edge_count] = w;
    next_edge[edge_count] = head[u];
    head[u] = edge_count++;
}

Для неориентированного графа каждое ребро добавляется дважды: add_edge(u, v, w) и add_edge(v, u, w).

Бинарная min-куча​

Куча хранит пары (расстояние, вершина). Операции heap_push и heap_pop работают за O(log k), где k — текущий размер кучи. Вместо операции decrease-key используется ленивое удаление: при релаксации в кучу добавляется новая запись, а устаревшие записи отбрасываются при извлечении.

typedef struct {
    int dist;
    int vertex;
} HeapNode;

HeapNode heap[MAX_E + 1];
int heap_size;

void heap_push(int dist, int vertex) {
    int i = heap_size++;
    heap[i].dist = dist;
    heap[i].vertex = vertex;
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[parent].dist <= heap[i].dist)
            break;
        HeapNode tmp = heap[parent];
        heap[parent] = heap[i];
        heap[i] = tmp;
        i = parent;
    }
}

HeapNode heap_pop(void) {
    HeapNode result = heap[0];
    heap[0] = heap[--heap_size];
    int i = 0;
    for (;;) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int smallest = i;
        if (left < heap_size && heap[left].dist < heap[smallest].dist)
            smallest = left;
        if (right < heap_size && heap[right].dist < heap[smallest].dist)
            smallest = right;
        if (smallest == i)
            break;
        HeapNode tmp = heap[i];
        heap[i] = heap[smallest];
        heap[smallest] = tmp;
        i = smallest;
    }
    return result;
}

Размер массива heap[] равен MAX_E + 1, потому что каждое ребро может породить не более одного push, плюс начальная вершина.

Основной алгоритм​

Массив dist[] хранит текущие кратчайшие расстояния, pred[] — предшественников для восстановления пути. Инициализация: dist[s] = 0, остальные — INF, все pred равны −1.

int dist[MAX_V];
int pred[MAX_V];

void dijkstra(int s, int n) {
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        pred[i] = -1;
    }
    dist[s] = 0;
    heap_size = 0;
    heap_push(0, s);

    while (heap_size > 0) {
        HeapNode cur = heap_pop();
        int v = cur.vertex;
        int d = cur.dist;

        if (d > dist[v])
            continue;  /* устаревшая запись */

        for (int e = head[v]; e != -1; e = next_edge[e]) {
            int u = to[e];
            int w = weight[e];
            if (dist[v] + w < dist[u]) {
                dist[u] = dist[v] + w;
                pred[u] = v;
                heap_push(dist[u], u);
            }
        }
    }
}

Ключевой момент — проверка if (d > dist[v]) continue. Без неё алгоритм обрабатывал бы устаревшие записи и мог бы выполнять лишние релаксации, хотя корректность не нарушилась бы. С проверкой каждая вершина обрабатывается не более одного раза.

Восстановление пути​

Массив pred[] позволяет восстановить кратчайший путь от s до любой достижимой вершины. Двигаемся от целевой вершины к источнику через предшественников, затем разворачиваем последовательность.

void print_path(int s, int t) {
    if (dist[t] == INF) {
        printf("Вершина %d недостижима из %d\n", t, s);
        return;
    }
    int path[MAX_V];
    int len = 0;
    for (int v = t; v != -1; v = pred[v])
        path[len++] = v;
    printf("Путь (длина %d): ", dist[t]);
    for (int i = len - 1; i >= 0; i--)
        printf("%d%s", path[i], i > 0 ? " -> " : "\n");
}

Если pred[t] остаётся −1 и t != s, вершина недостижима.

Полный пример с тестом​

int main(void) {
    int n = 5;
    init_graph(n);

    /* Неориентированный граф:
       0 --1-- 1 --2-- 2
       |               |
       4               1
       |               |
       3 ------3------ 4
    */
    add_edge(0, 1, 1); add_edge(1, 0, 1);
    add_edge(1, 2, 2); add_edge(2, 1, 2);
    add_edge(0, 3, 4); add_edge(3, 0, 4);
    add_edge(2, 4, 1); add_edge(4, 2, 1);
    add_edge(3, 4, 3); add_edge(4, 3, 3);

    dijkstra(0, n);

    for (int i = 0; i < n; i++)
        printf("dist[0->%d] = %d\n", i, dist[i] == INF ? -1 : dist[i]);

    print_path(0, 4);
    return 0;
}

Ожидаемый вывод:

dist[0->0] = 0
dist[0->1] = 1
dist[0->2] = 3
dist[0->3] = 4
dist[0->4] = 4
Путь (длина 4): 0 -> 1 -> 2 -> 4

Анализ сложности​

Операция	Стоимость	Количество
heap_push	O(log m)	не более m + 1
heap_pop	O(log m)	не более m + 1
Обход рёбер вершины	O(deg(v))	суммарно O(m)
Итого	O((n + m) log m)	—

Поскольку для простого графа m ≤ n(n−1)/2, величина log m ≤ 2 log n, и сложность записывается как O((n + m) log n). Для разреженных графов (m = O(n)) это O(n log n).

Пространственная сложность: O(n + m) на граф и O(m) на кучу в худшем случае.

Ограничения и типичные ошибки​

Отрицательные рёбра. Алгоритм Дейкстры некорректен при отрицательных весах. Если граф содержит такие рёбра, нужен алгоритм Беллмана–Форда.

Переполнение при сложении. Выражение dist[v] + w может переполниться, если dist[v] близко к INT_MAX. Безопасная проверка:

if (dist[v] != INF && dist[v] + w < dist[u]) { ... }

Для графов с большими весами используйте long long и соответствующую константу INF.

Размер кучи. При ленивом удалении куча может содержать до m + 1 элементов. Если MAX_E занижен, произойдёт выход за границы массива. Для динамического выделения памяти используйте malloc/realloc.

Неориентированный граф. Забудьте добавить обратное ребро — и часть вершин окажется недостижимой.

Несколько рёбер между парой вершин. Forward star корректно хранит параллельные рёбра; алгоритм выберет кратчайшее через релаксацию.

Проверка результата​

После запуска убедитесь:

• dist[s] == 0.
  
• Для каждого ребра (u, v, w) выполняется неравенство dist[v] <= dist[u] + w (условие оптимальности).
  
• Для каждой вершины с dist[v] < INF цепочка pred приводит к s.
  
• Если вершина недостижима, dist[v] == INF и pred[v] == -1.
  

Эти проверки можно автоматизировать в unit-тестах, что особенно полезно при модификации кода или переходе на другие структуры данных.

Источники​

• Dijkstra - finding shortest paths from given vertex - Algorithms for Competitive Programming
  
• Main Page - Algorithms for Competitive Programming