{ "type": "doc", "content": [ { "type": "heading", "attrs": { "level": 2 }, "content": [{ "type": "text", "text": "Короткий ответ" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Алгоритм Флойда–Уоршелла вычисляет кратчайшие пути между всеми парами вершин в взвешенном ориентированном графе (включая отрицательные веса рёбер, но без отрицательных циклов). Он возвращает матрицу кратчайших расстояний, может восстанавливать сами пути и позволяет обнаружить отрицательные циклы (dist[i][i] < 0). Сложность: O(V^3) по времени и O(V^2) по памяти." } ] }, { "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..k} и улучшаем известные расстояния между каждой парой (i, j)." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Основная релаксация: если dist[i][k] + dist[k][j] < dist[i][j], то обновляем dist[i][j] и запоминаем направление для восстановления пути." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Отрицательные циклы обнаруживаются по условию dist[v][v] < 0 хотя бы для одной вершины v." }] }] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Входные данные и соглашения" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Граф хранится как матрица смежности: adj[i][j] — вес ребра i → j, Infinity если ребра нет, 0 на диагонали." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Поддерживаются отрицательные веса рёбер, но алгоритм корректен только при отсутствии отрицательных циклов, достижимых из i в j." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Для неориентированного графа веса симметризуют: adj[u][v] = adj[v][u] = w." }] }] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Псевдокод" }] }, { "type": "codeBlock", "attrs": { "language": "text" }, "content": [ { "type": "text", "text": "dist = adj (скопировать матрицу)\nnext[i][j] = j, если есть ребро i→j, иначе null\nдля k в [0..n-1]:\n для i в [0..n-1]:\n для j в [0..n-1]:\n если dist[i][k] + dist[k][j] < dist[i][j]:\n dist[i][j] = dist[i][k] + dist[k][j]\n next[i][j] = next[i][k]\n\nестьОтрицЦикл = существует v: dist[v][v] < 0\nвосстановитьПуть(u, v): идти по next[u][v], пока не дойдём до v" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Реализация на JavaScript (с восстановлением пути и проверкой циклов)" }] }, { "type": "codeBlock", "attrs": { "language": "js" }, "content": [ { "type": "text", "text": "const INF = Infinity;\n\nfunction floydWarshall(adj) {\n const n = adj.length;\n const dist = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => adj[i][j]));\n const next = Array.from({ length: n }, () => Array(n).fill(null));\n\n // Инициализация\n for (let i = 0; i < n; i++) {\n for (let j = 0; j < n; j++) {\n if (i === j && dist[i][j] !== 0) dist[i][j] = 0;\n if (i !== j && dist[i][j] !== INF) next[i][j] = j;\n }\n }\n\n // Основные тройные циклы\n for (let k = 0; k < n; k++) {\n for (let i = 0; i < n; i++) {\n const dik = dist[i][k];\n if (dik === INF) continue;\n for (let j = 0; j < n; j++) {\n const dkj = dist[k][j];\n if (dkj === INF) continue;\n const alt = dik + dkj;\n if (alt < dist[i][j]) {\n dist[i][j] = alt;\n next[i][j] = next[i][k];\n }\n }\n }\n }\n\n // Обнаружение отрицательных циклов\n let hasNegativeCycle = false;\n const negativeCycleVertices = [];\n for (let v = 0; v < n; v++) {\n if (dist[v][v] < 0) {\n hasNegativeCycle = true;\n negativeCycleVertices.push(v);\n }\n }\n\n function reconstructPath(u, v) {\n if (next[u][v] == null) return null; // пути нет\n const path = [u];\n while (u !== v) {\n u = next[u][v];\n if (u == null) return null; // защита от несогласованных данных\n path.push(u);\n }\n return path;\n }\n\n return { dist, next, hasNegativeCycle, negativeCycleVertices, reconstructPath };\n}\n\n// Пример использования\n// Вершины: 0,1,2,3\n// Рёбра: 0→1(3), 0→2(8), 1→2(2), 1→3(5), 2→3(1), 3→1(-2)\nconst adj = [\n [0, 3, 8, INF],\n [INF, 0, 2, 5 ],\n [INF, INF, 0, 1 ],\n [INF,-2, INF, 0 ],\n];\n\nconst { dist, reconstructPath, hasNegativeCycle } = floydWarshall(adj);\nconsole.log('hasNegativeCycle:', hasNegativeCycle); // false\nconsole.log('dist matrix:');\nconsole.table(dist);\n\nconst path03 = reconstructPath(0, 3); // ожидаемо: [0,1,2,3]\nconsole.log('path 0→3:', path03);\n" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Результат для примера (кратчайшие расстояния)" }] }, { "type": "codeBlock", "attrs": { "language": "text" }, "content": [ { "type": "text", "text": "[\n [ 0, 3, 5, 6],\n [ INF, 0, 2, 3],\n [ INF, -1, 0, 1],\n [ INF, -2, 0, 0]\n]\n// Путь 0→3: 0 → 1 → 2 → 3, вес 6\n" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Обнаружение отрицательных циклов" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Если после выполнения алгоритма найдётся вершина v с dist[v][v] < 0, значит существует отрицательный цикл, достижимый из v. В этом случае любые пути, достигающие и покидающие этот цикл, не имеют конечной минимальной длины (их можно уменьшать бесконечно). Для практики:" } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Останавливайте восстановление пути, если маршрут заходит в подграф, достижимый от отрицательного цикла." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Иногда дополнительно «проталкивают» -Infinity вдоль рёбер, достижимых из отрицательных циклов, чтобы явно пометить такие расстояния как неограниченно малые." }] }] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Сложность и когда применять" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Время: O(V^3). Память: O(V^2)." }] }] }, { "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": "orderedList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Храните матрицу next: next[i][j] = первая вершина после i на кратчайшем пути к j." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Стартуйте с u, пока u != v: u = next[u][v], добавляя вершины в список." }] }] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Связь с алгоритмом Уоршелла (транзитивное замыкание)" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Если вместо чисел использовать булевы значения (есть ли путь), получаем алгоритм Уоршелла для транзитивного замыкания: reach[i][j] |= reach[i][k] && reach[k][j]. Это тот же шаблон тройного цикла." } ] }, { "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 всех кратчайших расстояний; опционально — матрицу next для восстановления пути." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Сложность? — O(V^3) время, O(V^2) память." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Когда лучше Дейкстра? — Когда граф без отрицательных рёбер и нужны пути из одной вершины; для всех пар — Дейкстру запускают V раз или используют Джонсон." }] }] } ] } ] }

Что делает алгоритм Флойда–Уоршелла на графах?

Комментарии