Wikiszótár

Bellman-Ford-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈbɛlmɒɱfordɒlɡoritmuʃ]

Főnév

Bellman-Ford-algoritmus

  1. (matematika, algoritmusok, gráfelmélet) A Bellman–Ford-algoritmus egy algoritmus, amely kiszámítja a legrövidebb utat egyetlen forrástól (vertex) az összes többi csúcshoz egy súlyozott digráfban.

Bellman-Ford-algoritmus bemutatása

A Bellman-Ford-algoritmus egy gráfkeresési algoritmus, amely egy adott kezdőcsúcsból hatékonyan meghatározza a legrövidebb útvonalat egy irányított, súlyozott gráf összes többi csúcsába. Az algoritmus képes kezelni negatív súlyú éleket, és észleli a negatív köröket (olyan köröket, amelyek súlyainak összege negatív).


Elmélet

Lépések:

  1. Távolságok inicializálása:
    • A kezdőcsúcs távolsága 0, minden más csúcs távolsága () (végtelen).
  2. Élek lazítása:
    • Minden csúcsra ismételd meg: lazítsd az összes él súlyát (V - 1) alkalommal (ahol (V) a csúcsok száma). Ez azt jelenti, hogy ha egy csúcsból egy szomszédba vezető út rövidebb, mint a jelenlegi ismert távolság, akkor frissítsük a távolságot.
  3. Negatív kör ellenőrzése:
    • Ha egy újabb lazítás során találunk olyan élt, amelyen keresztül tovább csökkenthető lenne egy távolság, az azt jelenti, hogy negatív súlyú kört találtunk.


Fontos tulajdonságok

  • Időkomplexitás: (O(V E)), ahol (V) a csúcsok, (E) az élek száma.
  • Térkomplexitás: (O(V)), mivel csak a távolságokat és a szülőket tároljuk.
  • Negatív körök észlelése: Egyetlen éllazítási iterációval (V - 1) kör után.


Pszeudokód

BellmanFord(G, start):
    Távolság = [végtelen] * G.csúcsok_száma
    Távolság[start] = 0
    
    ismételd (G.csúcsok_száma - 1) alkalommal:
        minden él (u, v, w) esetén:
            ha Távolság[u] + w < Távolság[v]:
                Távolság[v] = Távolság[u] + w

    minden él (u, v, w) esetén:
        ha Távolság[u] + w < Távolság[v]:
            negatív kör van

    visszatér Távolság

Python implementáció

def bellman_ford(graph, vertices, edges, start):
    # Távolságok inicializálása
    distances = [float('inf')] * vertices
    distances[start] = 0

    # Az élek lazítása V-1 alkalommal
    for _ in range(vertices - 1):
        for u, v, weight in edges:
            if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight

    # Negatív kör ellenőrzése
    for u, v, weight in edges:
        if distances[u] != float('inf') and distances[u] + weight < distances[v]:
            raise ValueError("Negatív súlyú kör található!")

    return distances

# Példa gráf (csúcsok: 5, élek: [(forrás, cél, súly)])
vertices = 5
edges = [
    (0, 1, -1),
    (0, 2, 4),
    (1, 2, 3),
    (1, 3, 2),
    (1, 4, 2),
    (3, 2, 5),
    (3, 1, 1),
    (4, 3, -3)
]

try:
    distances = bellman_ford(edges, vertices, edges, 0)
    print("Távolságok a 0. csúcsból:", distances)
except ValueError as e:
    print(e)

C++ implementáció

#include <iostream>
#include <vector>
#include <tuple>
#include <limits>

using namespace std;

// Bellman-Ford algoritmus megvalósítása
vector<int> bellman_ford(int vertices, vector<tuple<int, int, int>>& edges, int start) {
    // Távolságok inicializálása
    vector<int> distances(vertices, numeric_limits<int>::max());
    distances[start] = 0;

    // Élek lazítása V-1 alkalommal
    for (int i = 0; i < vertices - 1; ++i) {
        for (const auto& [u, v, weight] : edges) {
            if (distances[u] != numeric_limits<int>::max() && distances[u] + weight < distances[v]) {
                distances[v] = distances[u] + weight;
            }
        }
    }

    // Negatív kör ellenőrzése
    for (const auto& [u, v, weight] : edges) {
        if (distances[u] != numeric_limits<int>::max() && distances[u] + weight < distances[v]) {
            throw runtime_error("Negatív súlyú kör található!");
        }
    }

    return distances;
}

int main() {
    int vertices = 5;
    vector<tuple<int, int, int>> edges = {
        {0, 1, -1},
        {0, 2, 4},
        {1, 2, 3},
        {1, 3, 2},
        {1, 4, 2},
        {3, 2, 5},
        {3, 1, 1},
        {4, 3, -3}
    };

    try {
        vector<int> distances = bellman_ford(vertices, edges, 0);
        cout << "Távolságok a 0. csúcsból:" << endl;
        for (int i = 0; i < distances.size(); ++i) {
            cout << "0 -> " << i << ": " << distances[i] << endl;
        }
    } catch (const runtime_error& e) {
        cout << e.what() << endl;
    }

    return 0;
}

Összegzés

A Bellman-Ford-algoritmus erőteljes módszer a legrövidebb utak meghatározására súlyozott gráfokban, beleértve azokat, amelyek negatív súlyú éleket tartalmaznak. Képes felismerni negatív köröket, ezért különösen hasznos olyan problémákban, ahol ezek előfordulhatnak. Mind Pythonban, mind C++-ban könnyen implementálható, és széles körben alkalmazzák hálózatelemzésben, ütemezésben és egyéb algoritmikus problémák megoldására.

További információk

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