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).
BellmanFord(G, start):
Távolság = * G.csúcsok_száma
Távolság = 0
ismételd (G.csúcsok_száma - 1) alkalommal:
minden él (u, v, w) esetén:
ha Távolság + w < Távolság:
Távolság = Távolság + w
minden él (u, v, w) esetén:
ha Távolság + w < Távolság:
negatív kör van
visszatér Távolság
def bellman_ford(graph, vertices, edges, start):
# Távolságok inicializálása
distances = * vertices
distances = 0
# Az élek lazítása V-1 alkalommal
for _ in range(vertices - 1):
for u, v, weight in edges:
if distances != float('inf') and distances + weight < distances:
distances = distances + weight
# Negatív kör ellenőrzése
for u, v, weight in edges:
if distances != float('inf') and distances + weight < distances:
raise ValueError("Negatív súlyú kör található!")
return distances
# Példa gráf (csúcsok: 5, élek: )
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)
#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 = 0;
// Élek lazítása V-1 alkalommal
for (int i = 0; i < vertices - 1; ++i) {
for (const auto& : edges) {
if (distances != numeric_limits<int>::max() && distances + weight < distances) {
distances = distances + weight;
}
}
}
// Negatív kör ellenőrzése
for (const auto& : edges) {
if (distances != numeric_limits<int>::max() && distances + weight < distances) {
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 << endl;
}
} catch (const runtime_error& e) {
cout << e.what() << endl;
}
return 0;
}
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.