Az algoritmus iteratívan javítja a legrövidebb utak hosszát. Kezdetben a közvetlen élek súlyát vesszük figyelembe, majd minden iterációban megvizsgáljuk, hogy egy köztes csúcs (k)-n keresztül rövidebb út található-e.
FloydWarshall(G):
n = G.csúcsok_száma
D = mátrix(n x n) // Kezdeti távolságmátrix
inicializáld D-t G élsúlyaival
ciklus k = 1-től n-ig:
ciklus i = 1-től n-ig:
ciklus j = 1-től n-ig:
D = min(D, D + D)
visszatér D
def floyd_warshall(graph):
# Csúcsok száma
n = len(graph)
# Távolságmátrix inicializálása
dist = * n for _ in range(n)]
for i in range(n):
for j in range(n):
if i == j:
dist = 0 # Saját csúcsba való távolság 0
elif graph != 0:
dist = graph # Élek súlya
# Floyd-Warshall algoritmus
for k in range(n):
for i in range(n):
for j in range(n):
dist = min(dist, dist + dist)
return dist
# Példa gráf
graph = [
,
,
,
]
distances = floyd_warshall(graph)
for row in distances:
print(row)
Példa bemenet:
0 3 ∞ 5 2 0 ∞ 4 ∞ 1 0 ∞ ∞ ∞ 2 0
Példa kimenet:
0 3 7 5 2 0 6 4 3 1 0 5 5 3 2 0
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
const int INF = numeric_limits<int>::max();
void floydWarshall(vector<vector<int>>& graph) {
int n = graph.size();
vector<vector<int>> dist = graph;
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (dist != INF && dist != INF && dist + dist < dist) {
dist = dist + dist;
}
}
}
}
// Távolságok kiíratása
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (dist == INF) {
cout << "INF ";
} else {
cout << dist << " ";
}
}
cout << endl;
}
}
int main() {
vector<vector<int>> graph = {
{0, 3, INF, 5},
{2, 0, INF, 4},
{INF, 1, 0, INF},
{INF, INF, 2, 0}
};
floydWarshall(graph);
return 0;
}
Kimenet:
0 3 7 5 2 0 6 4 3 1 0 5 5 3 2 0
A Floyd-Warshall-algoritmus egy robusztus, egyszerű algoritmus az összes csúcspár közötti legrövidebb utak megtalálására. Bár időkomplexitása (O(V^3)), ami nagy gráfok esetén nem ideális, kis és közepes méretű gráfokon hatékony és könnyen implementálható. Az algoritmus emellett képes kezelni negatív súlyú éleket, de negatív súlyú körök esetén a probléma felismerésére is alkalmas.