{ "type": "doc", "content": [ { "type": "heading", "attrs": { "level": 2 }, "content": [{ "type": "text", "text": "Короткий ответ" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Алгоритм Дейкстры находит кратчайшие пути от одной стартовой вершины до всех остальных в ориентированном или неориентированном графе с неотрицательными весами рёбер. Он жадно выбирает вершину с минимальной текущей оценкой расстояния, «фиксирует» её ответ, а затем релаксирует рёбра, улучшая оценки соседей через эту вершину до тех пор, пока не обработает все достижимые вершины." } ] }, { "type": "heading", "attrs": { "level": 2 }, "content": [{ "type": "text", "text": "Подробное объяснение" }] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Когда применять" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Взвешенные графы с неотрицательными весами рёбер (>= 0)." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Ориентированные и неориентированные графы." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Задачи маршрутизации, поиска минимальной стоимости, оценки расстояний на сетях дорог, графах зависимостей и т. п." }] }] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Идея алгоритма" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Поддерживаем массив (или словарь) dist с лучшими известными расстояниями от источника s до всех вершин. Изначально dist[s] = 0, остальные = ∞. На каждом шаге выбираем незафиксированную вершину u с минимальным dist[u] (с помощью приоритетной очереди/кучи), фиксируем её как оптимальную и пытаемся улучшить расстояния до её соседей (релаксация)." } ] }, { "type": "orderedList", "attrs": { "start": 1 }, "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Инициализация: dist[source] = 0, для остальных ∞; parent[v] = null." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Помещаем source в приоритетную очередь по ключу dist." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Пока очередь не пуста: извлекаем вершину u с минимальным dist[u]. Если извлечённая оценка устарела — пропускаем." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Для каждого ребра (u → v) веса w ≥ 0 выполняем релаксацию: если dist[u] + w < dist[v], то обновляем dist[v] и parent[v] = u, кладём v в очередь с новым приоритетом dist[v]." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "После извлечения вершины u с минимальной оценкой её dist[u] становится окончательным (жадное свойство на неотрицательных весах)." }] }] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Почему это корректно (интуиция)" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Неотрицательные веса гарантируют, что «дешевле» уже не станет, если мы пойдём ещё дальше от вершины с минимальным известным расстоянием." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Инвариант: когда вершина извлечена из очереди, её dist — кратчайшее возможное расстояние от источника." }] }] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Сложность" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "С приоритетной очередью на бинарной куче и списками смежности: O((V + E) log V)." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "С массивом без кучи (поиск минимума за O(V) на каждом шаге): O(V^2), удобно для плотных графов или маленьких V." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "С Фибоначчиевой кучей: O(E + V log V) теоретически, но сложнее в реализации." }] }] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Структуры данных" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "dist[v] — лучшая текущая оценка расстояния." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "parent[v] — предок для восстановления пути." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Приоритетная очередь (минимальная куча) по ключу dist." }] }] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Пошаговый пример" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Граф (неориентированный для простоты, заменяем каждое ребро двумя противоположными):" } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "A — B (4), A — C (1)" }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "C — B (2), C — D (4)" }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "B — E (4), D — E (1)" }] }] } ] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Старт: A. Инициализация: dist[A]=0, остальные=∞." } ] }, { "type": "orderedList", "attrs": { "start": 1 }, "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Извлекаем A (0). Релаксации: B ← 4, C ← 1. dist: A=0, B=4, C=1, D=∞, E=∞." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Извлекаем C (1). Релаксации: B ← min(4, 1+2=3) → 3; D ← 1+4=5. dist: A=0, B=3, C=1, D=5, E=∞." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Извлекаем B (3). Релаксации: E ← 3+4=7. dist: A=0, B=3, C=1, D=5, E=7." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Извлекаем D (5). Релаксации: E ← min(7, 5+1=6) → 6. dist: A=0, B=3, C=1, D=5, E=6." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Извлекаем E (6). Готово. Кратчайший путь A → E имеет стоимость 6: A → C → D → E." }] } ] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Псевдокод" }] }, { "type": "codeBlock", "content": [ { "type": "text", "text": "function Dijkstra(G, source):\n for each v in G.V:\n dist[v] = INF\n parent[v] = null\n dist[source] = 0\n\n PQ = min-priority-queue()\n PQ.push(source, 0)\n\n while not PQ.empty():\n (u, du) = PQ.popMin() // вершина с минимальным текущим dist\n if du > dist[u]:\n continue // устаревшая запись\n\n for each (v, w) in G.adj[u]: // ребро u -> v с весом w\n if w < 0:\n error \"Dijkstra requires non-negative weights\"\n if dist[u] + w < dist[v]:\n dist[v] = dist[u] + w\n parent[v] = u\n PQ.push(v, dist[v])\n\n return dist, parent\n" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Реализация на JavaScript (с бинарной кучей)" }] }, { "type": "codeBlock", "content": [ { "type": "text", "text": "// Граф в виде списков смежности: { A: [{to: 'B', w: 4}, {to: 'C', w: 1}], ... }\nclass MinHeap {\n constructor() { this.a = []; }\n isEmpty() { return this.a.length === 0; }\n push(item) { this.a.push(item); this._siftUp(this.a.length - 1); }\n pop() {\n if (this.a.length === 0) return null;\n const top = this.a[0];\n const last = this.a.pop();\n if (this.a.length) { this.a[0] = last; this._siftDown(0); }\n return top;\n }\n _siftUp(i) {\n while (i > 0) {\n const p = (i - 1) >> 1;\n if (this.a[p].priority <= this.a[i].priority) break;\n [this.a[p], this.a[i]] = [this.a[i], this.a[p]];\n i = p;\n }\n }\n _siftDown(i) {\n const n = this.a.length;\n while (true) {\n let l = i * 2 + 1, r = i * 2 + 2, m = i;\n if (l < n && this.a[l].priority < this.a[m].priority) m = l;\n if (r < n && this.a[r].priority < this.a[m].priority) m = r;\n if (m === i) break;\n [this.a[i], this.a[m]] = [this.a[m], this.a[i]];\n i = m;\n }\n }\n}\n\nfunction dijkstra(graph, source) {\n const dist = Object.create(null);\n const parent = Object.create(null);\n const pq = new MinHeap();\n\n for (const v of Object.keys(graph)) {\n dist[v] = Infinity;\n parent[v] = null;\n }\n dist[source] = 0;\n pq.push({ node: source, priority: 0 });\n\n while (!pq.isEmpty()) {\n const { node: u, priority: du } = pq.pop();\n if (du > dist[u]) continue; // устаревшая запись\n\n for (const { to: v, w } of graph[u]) {\n if (w < 0) throw new Error('Dijkstra requires non-negative weights');\n const nd = dist[u] + w;\n if (nd < dist[v]) {\n dist[v] = nd;\n parent[v] = u;\n pq.push({ node: v, priority: nd });\n }\n }\n }\n\n return { dist, parent };\n}\n\nfunction reconstructPath(parent, source, target) {\n const path = [];\n let cur = target;\n if (parent[cur] === null && cur !== source) return []; // нет пути\n while (cur != null) {\n path.push(cur);\n if (cur === source) break;\n cur = parent[cur];\n }\n path.reverse();\n return path;\n}\n\n// Пример\nconst graph = {\n A: [{ to: 'B', w: 4 }, { to: 'C', w: 1 }],\n B: [{ to: 'A', w: 4 }, { to: 'C', w: 2 }, { to: 'E', w: 4 }],\n C: [{ to: 'A', w: 1 }, { to: 'B', w: 2 }, { to: 'D', w: 4 }],\n D: [{ to: 'C', w: 4 }, { to: 'E', w: 1 }],\n E: [{ to: 'B', w: 4 }, { to: 'D', w: 1 }]\n};\n\nconst { dist, parent } = dijkstra(graph, 'A');\nconsole.log(dist); // { A:0, B:3, C:1, D:5, E:6 }\nconsole.log(reconstructPath(parent, 'A', 'E')); // [ 'A', 'C', 'D', 'E' ]\n" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Как восстановить путь" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Держим parent[v] — предшественника на кратчайшем пути. После работы алгоритма идём от целевой вершины назад по parent до источника и разворачиваем последовательность." } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Крайние случаи и подводные камни" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Отрицательные рёбра/циклы не поддерживаются: используйте Беллмана–Форда или Johnson." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Несвязные графы: для недостижимых вершин dist останется ∞." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Ранний выход: если нужен путь только до одной цели t, можно остановиться сразу после извлечения t из очереди." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "0-1 веса: используйте 0-1 BFS (двухконцевая очередь) для O(V+E)." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Матрица смежности: для плотных графов удобно O(V^2) без кучи." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Двунаправленный поиск (bidirectional Dijkstra) ускоряет поиск между двумя вершинами в больших графах." }] }] } ] } ] }

Как работает алгоритм Дейкстры (Dijkstra) на графах?

Комментарии