Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Як працює алгоритм Дейкстри (Dijkstra) на графах?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

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

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

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

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

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

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

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

1. Видаляємо A (0). Релаксації: B ← 4, C ← 1. dist: A=0, B=4, C=1, D=∞, E=∞.
2. Видаляємо C (1). Релаксації: B ← min(4, 1+2=3) → 3; D ← 1+4=5. dist: A=0, B=3, C=1, D=5, E=∞.
3. Видаляємо B (3). Релаксації: E ← 3+4=7. dist: A=0, B=3, C=1, D=5, E=7.
4. Видаляємо D (5). Релаксації: E ← min(7, 5+1=6) → 6. dist: A=0, B=3, C=1, D=5, E=6.
5. Видаляємо 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) прискорює пошук між двома вершинами у великих графах.

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати1090 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.