Алгоритм Флойда-Уоршелла - алгоритм, который позволяет найти длины кратчайших путей
между всеми парами вершин во взвешенном графе, если в нём нет отрицательного цикла.
Разберём алгоритм на примере:
Пусть дан следующий граф:
Сначала необходимо инициализировать матрицу расстояний между всеми парами вершин.
Изначально все расстояния принимаются за бесконечность.
Расстояние из i-ой вершины в саму себя устанавливается на 0.
Также устанавливаются расстояния между соседними вершинами,
равные весу соединяющего их ребра.
Теперь для пары вершин необходимо пересчитать кратчайшее расстояние
через третью вершину k:
,
Где: - расстояние из вершины X в вершину Y; i, j, k - любые вершины в графе; i, j и k могут совпадать.
Кратчайшее расстояние из в :
Итерация для k = A закончилась, матрица кратчайших расстояний выглядит так:
Далее необходимо произвести те же действия для k = B, C, D.
После итерации k = B изменилось кратчайшее расстояние из A в D:
После итерации k = С изменились кратчайшие расстояния из A в D и из B в D:
После итерации k = D матрица кратчайших расстояний не изменилась:
Если в матрице кратчайших расстояний на её главной диагонали присутствуют
элементы меньшие нуля, то в данном графе существует отрицательный цикл.
Временная сложность - , пространственная - , где - множество вершин графа.
Аннотация:
FloydWarshell - алгоритм Флойда-Уоршелла
graph - матрица смежности, в которой хранится граф
vertexes - список вершин графа
dist - матрица расстояний, заполненная бесконечностями
Функция FloydWarshell(graph)
для вершины i в vertexes
dists[i][i] <- 0
для вершины j в vertexes
если graph[i][j] это не бесконечность
dists[i][j] <- graph[i][j]
для вершины k в vertexes
для вершины i в vertexes
для вершины j в vertexes
dist[i][j] <- минимум(dist[i][j], dist[i][k] + dist[k][j])
вернуть dist
Аннотация:
floyd_warshall - алгоритм Флойда-Уоршелла
graph - матрица смежности, в которой хранится граф
vertexes - количество вершин в графе
dists - матрица кратчайших расстояний между всеми парами вершин
inf - бесконечность, используемая для инициализации матрицы расстояний
isfinite - функция из модуля math для проверки конечности значения
def floyd_warshall(graph):
vertexes = len(graph)
dists = [[float('inf')] * v for _ in range(v)]
for i in range(v):
dists[i][i] = 0
for j in range(v):
if math.isfinite(graph[i][j]):
dists[i][j] = graph[i][j]
for k in range(v):
for i in range(v):
for j in range(v):
dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j])
return dists
Аннотация:
typedef - переопределение имени типа данных
floyd - алгоритм Флойда-Уоршелла
v - количество вершин в графе
d - инициализация диагональных элементов матрицы расстояний
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
const int INF = numeric_limits<int>::max();
vvi floyd(vvi& g) {
auto v = g.size();
vvi d(v, vi(v, INF));
for (int i = 0; i < v; ++i) {
d[i][i] = 0;
for (int j = 0; j < v; ++j)
if (g[i][j] != INF)
d[i][j] = g[i][j];
}
for (int k = 0; k < v; ++k)
for (int i = 0; i < v; ++i)
for (int j = 0; j < v; ++j)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
return d;
}
Аннотация:
floyd_warshall - алгоритм Флойда-Уоршелла
vertexes - количество вершин в графе
distances - матрица расстояний, инициализированная бесконечностями
const int INF = std::numeric_limits<int>::max();
std::vector<std::vector<int>> floyd_warshall(
const std::vector<std::vector<int>> &graph) {
auto vertexes = vertexes();
std::vector<std::vector<int>> distances(vertexes, std::vector<int>(vertexes, INF));
for (int v1 = 0; v1 < vertexs; ++v1) {
distances[v1][v1] = 0;
for (int v2 = 0; v2 < vertexes; ++v2)
if (graph[v1][v2] != INF)
distances[v1][v2] = graph[v1][v2];
}
for (int v1 = 0; v1 < vertexes; ++v1)
for (int v2 = 0; v2 < vertexes; ++v2)
for (int v3 = 0; v3 < vertexes; ++v3)
distances[v2][v3] = std::min(distances[v2][v3],
distances[v2][v1] + distances[v1][v3]);
return distances;
}