Алгоритм Дейкстри: доведення коректності

Постановка задачі та позначення

Нехай G = (V, E) — орієнтований зважений граф з невід'ємними вагами ребер w(u, v) ≥ 0, і вершина-джерело s. Позначимо δ(s, v) як справжню відстань найкоротшого шляху від s до v (величину, яку ми хочемо обчислити). Алгоритм Дейкстри підтримує для кожної вершини v оцінку d[v], яка починається з ∞ (крім d[s] = 0) і лише зменшується.

Алгоритм

Дейкстра підтримує множину S «завершених» вершин (чия найкоротша відстань остаточно визначена) і повторно вилучає незавершену вершину u з найменшим d[u], додаючи її до S, а потім релаксує кожне вихідне ребро (u, v):

Усе доведення коректності спирається на одну властивість RELAX: вона ніколи не робить d[v] меншим за δ(s, v) — вона може лише наближатись до істини зверху, ніколи не «перестрибуючи» знизу.

Інваріант релаксації

Лема (властивість верхньої межі): у будь-який момент виконання алгоритму d[v] ≥ δ(s, v) для кожної вершини v.

Доведення індукцією за кількістю викликів RELAX. Спочатку d[s] = 0 = δ(s, s), а d[v] = ∞ ≥ δ(s, v) для всіх інших v — базовий випадок тривіально виконується. Припустимо, що інваріант виконується перед викликом RELAX(u, v, w). Якщо виклик змінює d[v], нове значення дорівнює d[u] + w(u, v). За індуктивним припущенням d[u] ≥ δ(s, u), тому:

Отже, інваріант зберігається при кожному виклику RELAX, і за індукцією виконується протягом усього виконання. Цей єдиний факт — d ніколи не опускається нижче істини — є несучою стіною всього доведення.

Доведення індукцією за порядком завершення

Теорема: коли алгоритм Дейкстри додає вершину u до S (завершує її), d[u] = δ(s, u).

Доведення сильною індукцією за порядком завершення вершин. Нехай u — k-та завершена вершина, і припустимо, що теорема виконується для перших k − 1 завершених вершин.

Розгляньмо справжній найкоротший шлях P від s до u. Нехай y — перша вершина на P, яка ще не в S у момент завершення u (можливо y = u, якщо весь шлях уже завершений до u), а x — її попередник на P (x ∈ S, або x = s). Оскільки всі ваги ребер невід'ємні, і оскільки x був завершений до u, RELAX(x, y, ·) було викликано, коли x завершувався, тому за доведеним вище інваріантом:

Тепер, оскільки ваги ребер невід'ємні, кожна вершина після y на шляху P (включно з самою u) знаходиться не ближче до s, ніж y: δ(s, y) ≤ δ(s, u). Але Дейкстра обрав саме u (не y) як вершину з мінімальним значенням d серед усіх незавершених вершин, тому d[u] ≤ d[y] = δ(s, y) ≤ δ(s, u). Разом з лемою про верхню межу d[u] ≥ δ(s, u), отримуємо d[u] = δ(s, u). ∎

Жадібний аргумент обміну

Еквівалентний, більш інтуїтивний спосіб побачити той самий результат: Дейкстра — це жадібний алгоритм, а жадібні алгоритми коректні саме тоді, коли виконуються і «властивість жадібного вибору», і «оптимальна підструктура».

• Оптимальна підструктура: будь-який підшлях найкоротшого шляху сам є найкоротшим шляхом між своїми кінцями — тривіально істинно, оскільки коротший підшлях дав би коротший загальний шлях.
• Властивість жадібного вибору: серед усіх незавершених вершин та, що має найменшу тимчасову відстань, уже має свою остаточну, правильну відстань — саме це встановлює індукція вище.

Оскільки обидві властивості виконуються при невід'ємних вагах, аргумент обміну доходить висновку: заміна жадібного вибору будь-яким іншим не може покращити рішення, тому жадібна стратегія оптимальна на кожному кроці, а отже, глобально оптимальна.

Чому від'ємні ваги ламають доведення

Розгляньмо s → a (вага 2), s → b (вага 1), a → b (вага −3). Після релаксації обох ребер із s: d[a] = 2, d[b] = 1, тому Дейкстра завершує b першим (найменша тимчасова відстань) — ще до того, як буде оброблено вершину a, яка утримує єдине ребро, здатне покращити відстань до b. Щойно b завершено, алгоритм більше ніколи не релаксує ребро, що веде до нього.

Реалізація на пріоритетній черзі

function dijkstra(graph, source) {
  // graph: Map<вершина, Array<[сусід, вага]>>, всі ваги >= 0
  const dist = new Map();
  const prev = new Map();
  const settled = new Set();
  const pq = new MinHeap();  // бінарна мін-купа за ключем-відстанню

  for (const v of graph.keys()) dist.set(v, Infinity);
  dist.set(source, 0);
  pq.push(source, 0);

  while (!pq.isEmpty()) {
    const u = pq.pop();          // вершина з найменшою тимчасовою відстанню
    if (settled.has(u)) continue;  // застарілий запис купи — пропустити
    settled.add(u);                // u тепер остаточно завершено

    for (const [v, w] of graph.get(u)) {
      if (settled.has(v)) continue;
      const candidate = dist.get(u) + w;
      if (candidate < dist.get(v)) {   // крок RELAX
        dist.set(v, candidate);
        prev.set(v, u);
        pq.push(v, candidate);
      }
    }
  }
  return { dist, prev };
}

Підсумок складності

Для щільних графів (E ≈ V²) проста реалізація на масиві насправді найшвидша на практиці через низькі сталі множники. Для розріджених графів — типового випадку в дорожніх мережах та ігрових картах — стандартним вибором є версія з бінарною купою.