← Назад к графовым алгоритмам

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

Поиск кратчайших расстояний от стартовой вершины (O(n²))

🐍 Python
INF = 10**10
D = [INF] * n
D[s] = 0
used = [0] * n
md = 0
mv = s

while md < INF:
    i = mv
    used[i] = 1
    for j in range(n):
        if D[i] + W[i][j] < D[j]:
            D[j] = D[i] + W[i][j]
    md = INF
    for j in range(n):
        if used[j] == 0 and D[j] < md:
            md = D[j]
            mv = j

# D[t] — кратчайшее расстояние от s до t
⚙️ C++
const T INF = 1e10;
T md = 0, mv = s;

vector<T> D(n, INF);
D[s] = 0;

vector<T> used(n, 0);

while (md < INF) {
    i = mv;
    used[i] = 1;
    
    for (j = 0; j < n; j++) {
        if (D[i] + W[i][j] < D[j]) {
            D[j] = D[i] + W[i][j];
        }
    }
    
    md = INF;
    for (j = 0; j < n; j++) {
        if (!used[j] && D[j] < md) {
            md = D[j];
            mv = j;
        }
    }
}

// D[t] — кратчайшее расстояние от s до t

Как работает алгоритм Дейкстры?

Алгоритм Дейкстры находит кратчайшие расстояния от стартовой вершины s до всех остальных вершин во взвешенном графе с неотрицательными весами рёбер.

Инициализация

Основной цикл while (md < INF)

Пока есть необработанные вершины с конечным расстоянием:

  1. Выбор текущей вершины: берётся вершина i = mv с наименьшим известным расстоянием
  2. Пометка как обработанной: used[i] = 1
  3. Релаксация рёбер: для всех соседей j проверяется: если путь через i короче текущего известного расстояния до j, то расстояние обновляется: D[j] = D[i] + W[i][j]
  4. Поиск следующей вершины: среди всех необработанных вершин ищется вершина с минимальным расстоянием D[j]. Эта вершина становится новой mv для следующей итерации

Особенности реализации

В данной реализации используется наивный поиск минимальной вершины — полный перебор всех вершин на каждом шаге.

Временная сложность: O(n²), где n — количество вершин.

Требования: веса рёбер должны быть неотрицательными. При наличии отрицательных весов алгоритм может работать некорректно.

Пример работы

Рассмотрим граф из 4 вершин с весами:

Матрица весов W (n=4):
        0   1   2   3
    0   0   5   3   ∞
    1   5   0   2   7
    2   3   2   0   4
    3   ∞   7   4   0

Стартовая вершина: s = 0

Шаги алгоритма:

Инициализация: D = [0, ∞, ∞, ∞], used = [0,0,0,0], mv = 0

Шаг 1: берём i=0 (расстояние 0), помечаем used[0]=1
       релаксация: D[1] = 5, D[2] = 3
       ищем min среди необработанных: D[2]=3 → mv=2

Шаг 2: берём i=2 (расстояние 3), помечаем used[2]=1
       релаксация: D[1] = min(5, 3+2=5) = 5, D[3] = 3+4=7
       ищем min: D[1]=5 → mv=1

Шаг 3: берём i=1 (расстояние 5), помечаем used[1]=1
       релаксация: D[3] = min(7, 5+7=12) = 7
       ищем min: D[3]=7 → mv=3

Шаг 4: берём i=3 (расстояние 7), помечаем used[3]=1
       релаксация: нет непосещённых соседей
       все вершины обработаны → завершение

Результат: D = [0, 5, 3, 7]

Кратчайшие расстояния от вершины 0:
до 1: 5, до 2: 3, до 3: 7

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

Введите матрицу смежности (веса) и стартовую вершину:

Результат появится здесь...