Як працює алгоритм Дейкстри (Dijkstra) на графах?

АлгоритмиJunior~3 хв читання

Коротка відповідь

Алгоритм Дейкстри знаходить найкоротші шляхи від однієї стартової вершини до всіх інших в орієнтованому або неорієнтованому графі з невід'ємними вагами ребер. Він жадібно обирає вершину з мінімальною поточною оцінкою відстані, «фіксує» її відповідь, а потім релаксує ребра, покращуючи оцінки сусідів через цю вершину, доки не обробить усі досяжні вершини.

Детальне пояснення

Коли застосовувати

Зважені графи з невід'ємними вагами ребер (>= 0).
Орієнтовані та неорієнтовані графи.
Задачі маршрутизації, пошуку мінімальної вартості, оцінки відстаней на мережах доріг, графах залежностей тощо.

Ідея алгоритму

Підтримуємо масив (або словник) dist із найкращими відомими відстанями від джерела s до всіх вершин. Спочатку dist[s] = 0, інші = ∞. На кожному кроці обираємо незафіксовану вершину u з мінімальним dist[u] (за допомогою пріоритетної черги/купи), фіксуємо її як оптимальну і намагаємося покращити відстані до її сусідів (релаксація).

Ініціалізація: dist[source] = 0, для інших ∞; parent[v] = null.
Розміщуємо source в пріоритетній черзі за ключем dist.
Поки черга не порожня: видаляємо вершину u з мінімальним dist[u]. Якщо видалена оцінка застаріла - пропускаємо.
Для кожного ребра (u → v) ваги w ≥ 0 виконуємо релаксацію: якщо dist[u] + w < dist[v], оновлюємо dist[v] і parent[v] = u, кладемо v у чергу з новим пріоритетом dist[v].
Після видалення вершини u з мінімальною оцінкою її dist[u] стає остаточним (жадібна властивість за невід'ємних ваг).

Чому це коректно (інтуїція)

Невід'ємні ваги гарантують, що «дешевше» вже не стане, якщо ми підемо ще далі від вершини з мінімальною відомою відстанню.
Інваріант: коли вершину видалено з черги, її dist - найкоротша можлива відстань від джерела.

Складність

З пріоритетною чергою на бінарній купі та списками суміжності: O((V + E) log V).
З масивом без купи (пошук мінімуму за O(V) на кожному кроці): O(V^2), зручно для щільних графів або малих V.
З купою Фібоначчі: O(E + V log V) теоретично, але складніше в реалізації.

Структури даних

dist[v] - найкраща поточна оцінка відстані.
parent[v] - предок для відновлення шляху.
Пріоритетна черга (мінімальна купа) за ключем dist.

Покроковий приклад

Граф (неорієнтований для простоти, замінюємо кожне ребро двома протилежними):

A-B (4), A-C (1)
C-B (2), C-D (4)
B-E (4), D-E (1)

Старт: A. Ініціалізація: dist[A]=0, інші=∞.

Видаляємо A (0). Релаксації: B ← 4, C ← 1. dist: A=0, B=4, C=1, D=∞, E=∞.
Видаляємо C (1). Релаксації: B ← min(4, 1+2=3) → 3; D ← 1+4=5. dist: A=0, B=3, C=1, D=5, E=∞.
Видаляємо B (3). Релаксації: E ← 3+4=7. dist: A=0, B=3, C=1, D=5, E=7.
Видаляємо D (5). Релаксації: E ← min(7, 5+1=6) → 6. dist: A=0, B=3, C=1, D=5, E=6.
Видаляємо E (6). Готово. Найкоротший шлях A → E має вартість 6: A → C → D → E.

Псевдокод

function Dijkstra(G, source):
  for each v in G.V:
    dist[v] = INF
    parent[v] = null
  dist[source] = 0

  PQ = min-priority-queue()
  PQ.push(source, 0)

  while not PQ.empty():
    (u, du) = PQ.popMin()           // вершина з мінімальним поточним dist
    if du > dist[u]:
      continue                      // застарілий запис

    for each (v, w) in G.adj[u]:    // ребро u -> v з вагою w
      if w < 0:
        error "Dijkstra requires non-negative weights"
      if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        parent[v] = u
        PQ.push(v, dist[v])

  return dist, parent

Реалізація на JavaScript (з бінарною купою)

// Граф у вигляді списків суміжності: { A: [{to: 'B', w: 4}, {to: 'C', w: 1}], ... }
class MinHeap {
  constructor() { this.a = []; }
  isEmpty() { return this.a.length === 0; }
  push(item) { this.a.push(item); this._siftUp(this.a.length - 1); }
  pop() {
    if (this.a.length === 0) return null;
    const top = this.a[0];
    const last = this.a.pop();
    if (this.a.length) { this.a[0] = last; this._siftDown(0); }
    return top;
  }
  _siftUp(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.a[p].priority <= this.a[i].priority) break;
      [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
      i = p;
    }
  }
  _siftDown(i) {
    const n = this.a.length;
    while (true) {
      let l = i * 2 + 1, r = i * 2 + 2, m = i;
      if (l < n && this.a[l].priority < this.a[m].priority) m = l;
      if (r < n && this.a[r].priority < this.a[m].priority) m = r;
      if (m === i) break;
      [this.a[i], this.a[m]] = [this.a[m], this.a[i]];
      i = m;
    }
  }
}

function dijkstra(graph, source) {
  const dist = Object.create(null);
  const parent = Object.create(null);
  const pq = new MinHeap();

  for (const v of Object.keys(graph)) {
    dist[v] = Infinity;
    parent[v] = null;
  }
  dist[source] = 0;
  pq.push({ node: source, priority: 0 });

  while (!pq.isEmpty()) {
    const { node: u, priority: du } = pq.pop();
    if (du > dist[u]) continue; // застарілий запис

    for (const { to: v, w } of graph[u]) {
      if (w < 0) throw new Error('Dijkstra requires non-negative weights');
      const nd = dist[u] + w;
      if (nd < dist[v]) {
        dist[v] = nd;
        parent[v] = u;
        pq.push({ node: v, priority: nd });
      }
    }
  }

  return { dist, parent };
}

function reconstructPath(parent, source, target) {
  const path = [];
  let cur = target;
  if (parent[cur] === null && cur !== source) return []; // шляху немає
  while (cur != null) {
    path.push(cur);
    if (cur === source) break;
    cur = parent[cur];
  }
  path.reverse();
  return path;
}

// Приклад
const graph = {
  A: [{ to: 'B', w: 4 }, { to: 'C', w: 1 }],
  B: [{ to: 'A', w: 4 }, { to: 'C', w: 2 }, { to: 'E', w: 4 }],
  C: [{ to: 'A', w: 1 }, { to: 'B', w: 2 }, { to: 'D', w: 4 }],
  D: [{ to: 'C', w: 4 }, { to: 'E', w: 1 }],
  E: [{ to: 'B', w: 4 }, { to: 'D', w: 1 }]
};

const { dist, parent } = dijkstra(graph, 'A');
console.log(dist); // { A:0, B:3, C:1, D:5, E:6 }
console.log(reconstructPath(parent, 'A', 'E')); // [ 'A', 'C', 'D', 'E' ]

Як відновити шлях

Зберігаємо parent[v] - попередника на найкоротшому шляху. Після роботи алгоритму йдемо від цільової вершини назад по parent до джерела і розвертаємо послідовність.

Крайні випадки та підводні камені

Від'ємні ребра/цикли не підтримуються: використовуйте Беллмана-Форда або Johnson.
Незв'язні графи: для недосяжних вершин dist залишиться ∞.
Ранній вихід: якщо потрібен шлях лише до однієї цілі t, можна зупинитися одразу після видалення t з черги.
Ваги 0-1: використовуйте 0-1 BFS (двосторонню чергу) для O(V+E).
Матриця суміжності: для щільних графів зручно O(V^2) без купи.
Двонапрямлений пошук (bidirectional Dijkstra) прискорює пошук між двома вершинами у великих графах.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.