Алгоритм Флойда-Уоршелла
Описание
Алгоритм Флойда-Уоршелла (Floyd-Warshall algorithm) - это алгоритм поиска кратчайших путей во взвешенном графе с положительным или отрицательным весом ребер (но без отрицательных циклов). За одно выполнение алгоритма будут найдены длины (суммарные веса) кратчайших путей между всеми парами вершин. Хотя он не возвращает детали самих путей, можно реконструировать пути с помощью простых модификаций алгоритма.
Принцип работы
Алгоритм Флойда-Уоршелла сравнивает все возможные пути через граф между каждой парой вершин. Он может сделать это за O(V^3) сравнений в графе, даже если в графе может быть до V^2 ребер, и каждая комбинация ребер проверяется. Это достигается путем постепенного улучшения оценки кратчайшего пути между двумя вершинами, пока оценка не станет оптимальной.
Рассмотрим граф G с вершинами V, пронумерованными от 1 до N и функцию shortestPath(i, j, k), которая возвращает кратчайший возможный путь от i до j с использованием вершин только из множества {1, 2, ..., k} в качестве промежуточных точек на этом пути. Теперь, учитывая эту функцию, наша цель - найти кратчайший путь от каждого i до каждого j, используя любую вершину в {1, 2, ..., N}.
Если w(i,j) - вес ребра между вершинами i и j, мы можем определить shortestPath(i, j, k) следующим образом:
базовый случай
и рекурсивный случай
Эта формула составляет основу рассматриваемого алгоритма.
Пример
Пример выполнения алгоритма на графе слева внизу:
Матрица расстояний на каждой итерации k (обновленные расстояния выделены жирным шрифтом) будет иметь вид:
k = 0
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | ∞ | −2 | ∞ |
| 2 | 4 | 0 | 3 | ∞ |
| 3 | ∞ | ∞ | 0 | 2 |
| 4 | ∞ | −1 | ∞ | 0 |
k = 1
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | ∞ | −2 | ∞ |
| 2 | 4 | 0 | 2 | ∞ |
| 3 | ∞ | ∞ | 0 | 2 |
| 4 | ∞ | − | ∞ | 0 |
k = 2
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | ∞ | −2 | ∞ |
| 2 | 4 | 0 | 2 | ∞ |
| 3 | ∞ | ∞ | 0 | 2 |
| 4 | 3 | −1 | 1 | 0 |
k = 3
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | ∞ | −2 | 0 |
| 2 | 4 | 0 | 2 | 4 |
| 3 | ∞ | ∞ | 0 | 2 |
| 4 | 3 | −1 | 1 | 0 |
k = 4
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | −1 | −2 | 0 |
| 2 | 4 | 0 | 2 | 4 |
| 3 | 5 | 1 | 0 | 2 |
| 4 | 3 | −1 | 1 | 0 |
Реализация
// algorithms/graphs/floyd-warshall.js
// Функция принимает граф
export default function floydWarshall(graph) {
// Извлекаем все вершины
const vertices = graph.getAllNodes()
// Инициализируем матрицу предыдущих вершин
const nextVertices = Array(vertices.length)
.fill(null)
.map(() => {
return Array(vertices.length).fill(null)
})
// Инициализируем матрицу расстояний
const distances = Array(vertices.length)
.fill(null)
.map(() => {
return Array(vertices.length).fill(Infinity)
})
// Инициализируем `distances` расстояниями,
// которые нам уже известны (из имеющихся ребер).
// Также инициализируем матрицу предыдущих вершин
vertices.forEach((startNode, startIndex) => {
vertices.forEach((endNode, endIndex) => {
if (startNode === endNode) {
// Расстояние вершины до самой себя составляет 0
distances[startIndex][endIndex] = 0
} else {
// Находим ребро между начальной и конечной вершинами
const edge = graph.findEdge(startNode, endNode)
// Если такое ребро имеется
if (edge) {
// Сохраняем расстояние и предыдущую вершину
distances[startIndex][endIndex] = edge.weight
nextVertices[startIndex][endIndex] = startNode
} else {
distances[startIndex][endIndex] = Infinity
}
}
})
})
// Переходим к основной части алгоритма.
// Объединяем все вершины в пары (от начала до конца) и проверяем,
// существует ли между ними более короткий путь через среднюю вершину.
// Средняя вершина также может быть одной из вершин графа.
// Таким образом, нам требуется три цикла по всем вершинам графа:
// для начальной, конечной и средней вершин
vertices.forEach((middleNode, middleIndex) => {
// Путь начинается от `startNode` с `startIndex`
vertices.forEach((_startNode, startIndex) => {
// Путь заканчивается `endNode` с `endIndex`
vertices.forEach((_endNode, endIndex) => {
// Сравниваем существующее расстояние от `startNode` до `endNode`,
// с расстоянием от `startNode` до `endNode`, но через `middleNode`.
// Сохраняем кратчайшее расстояние и предыдущую вершину,
// предоставляющую этот кратчайший путь
const distViaMiddle =
distances[startIndex][middleIndex] + distances[middleIndex][endIndex]
if (distances[startIndex][endIndex] > distViaMiddle) {
// Мы нашли более короткий путь через `middleNode`
distances[startIndex][endIndex] = distViaMiddle
nextVertices[startIndex][endIndex] = middleNode
}
})
})
})
// Кратчайшее расстояние от `x` до `y`: `distance[x][y]`.
// Следующая вершина после `x` на пути от `x` до `y`: `nextVertices[x][y]`
return { distances, nextVertices }
}
Тесты
Запускаем тесты:
npm run test ./algorithms/graphs/__tests__/floyd-warshall
