Wikiszótár

Floyd-Warshall-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈfloidvɒrʃhɒlːɒlɡoritmuʃ]

Főnév

Floyd-Warshall-algoritmus

  1. (matematika, algoritmusok, gráfelmélet) A Floyd-Warshall-algoritmus egy dinamikus programozási technikán alapuló algoritmus, amely egy súlyozott gráf összes csúcspárja közötti legrövidebb útvonalat határozza meg. Az algoritmus irányított és irányítatlan gráfokon egyaránt működik, és negatív élű gráfokat is kezel, feltéve, hogy nincsenek negatív súlyú körök.


Elmélet

Algoritmus alapelve

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.

  • D(i, j): Az (i)-ből (j)-be vezető legrövidebb út hossza.
  • Alaphelyzet: [ D(i, j) = ]
  • Rekurzív formula: [ D(i, j) = (D(i, j), D(i, k) + D(k, j)), ] ahol (k) az aktuálisan vizsgált köztes csúcs.

Fontos tulajdonságok

  • Időkomplexitás: (O(V^3)), ahol (V) a csúcsok száma.
  • Térkomplexitás: (O(V^2)), mivel egy távolságmátrixot használunk.
  • Negatív körök kezelése: Ha a főátló mentén egy érték negatívvá válik ((D(i, i) < 0)), akkor negatív súlyú kör van a gráfban.


Pszeudokód

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[i][j] = min(D[i][j], D[i][k] + D[k][j])

    visszatér D

Python implementáció

def floyd_warshall(graph):
    # Csúcsok száma
    n = len(graph)
    # Távolságmátrix inicializálása
    dist = [[float('inf')] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if i == j:
                dist[i][j] = 0  # Saját csúcsba való távolság 0
            elif graph[i][j] != 0:
                dist[i][j] = graph[i][j]  # Élek súlya

    # Floyd-Warshall algoritmus
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

# Példa gráf
graph = [
    [0, 3, float('inf'), 5],
    [2, 0, float('inf'), 4],
    [float('inf'), 1, 0, float('inf')],
    [float('inf'), float('inf'), 2, 0]
]

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

C++ implementáció

#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[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // Távolságok kiíratása
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (dist[i][j] == INF) {
                cout << "INF ";
            } else {
                cout << dist[i][j] << " ";
            }
        }
        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

Összegzés

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.


Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Floyd-Warshall-algoritmus&oldid=3479455”