Описание тега floyd-warshall
Алгоритм Флойда-Уоршалла представляет собой алгоритм O(|V|^3) для вычисления кратчайших путей для всех пар в ориентированном взвешенном графе.
В процессе работы алгоритма Флойда – Уоршалла сравниваются все возможные пути через ориентированный взвешенный граф между каждой парой вершин. СложностьO(n^3) где n - количество вершин.
Минимальный псевдокод для получения только кратчайших путей графа:
for k = 1 to n
for i = 1 to n
for j = 1 to n
W[i][j] = min(W[i][j], W[i][k] + W[k][j])
где W матрица (размер n x n), в котором хранятся все кратчайшие пути. На стартеWзаполняется бесконечностью (любым большим числом, превышающим сумму весов графа). Для каждого края(u,v) графа вес ребра (u,v) должен быть помещен в матрицу W.
В алгоритме допускается реконструкция пути.
Этот алгоритм эффективен для полностью упакованного графа, особенно хранимого в виде матрицы связности.