83 lines
2.7 KiB
Python
83 lines
2.7 KiB
Python
from vorlesung.L08_graphen.graph import AdjacencyListGraph
|
||
|
||
# Korrigierte Kantenliste (Vorlesungsbeispiel).
|
||
# Hinweis: Das Arbeitsblatt enthält c->b:-2, c->e:5, d->c:-5, e->c:4 –
|
||
# diese Werte erzeugen einen negativen Zyklus (b->c->b: 1-2=-1) im
|
||
# Basisgraphen und müssen in der Aufgabenstellung korrigiert werden.
|
||
# Korrekte Werte (kein Vorzyklus, Ergebnis: b=7, c=2, d=4, e=6):
|
||
EDGES = [
|
||
('a', 'b', 9),
|
||
('a', 'd', 4),
|
||
('b', 'c', 1),
|
||
('b', 'd', 2),
|
||
('c', 'b', 5), # war -2 im Entwurf
|
||
('c', 'e', 4), # war 5 im Entwurf
|
||
('d', 'c', -2), # war -5 im Entwurf
|
||
('d', 'e', 2),
|
||
]
|
||
|
||
|
||
def bellman_ford(graph, start_name):
|
||
"""Bellman-Ford: kürzeste Wege mit Erkennung negativer Zyklen.
|
||
|
||
Gibt (distance_map, predecessor_map, has_negative_cycle) zurück.
|
||
|V|-1 Relaxationsdurchläufe über alle Kanten, dann ein Prüfdurchlauf.
|
||
"""
|
||
distance_map = {}
|
||
predecessor_map = {}
|
||
for v in graph.all_vertices():
|
||
distance_map[v] = float('inf')
|
||
predecessor_map[v] = None
|
||
|
||
start = graph.get_vertex(start_name)
|
||
distance_map[start] = 0
|
||
|
||
n = len(list(graph.all_vertices()))
|
||
for _ in range(n - 1):
|
||
for src_name, dst_name, weight in graph.all_edges():
|
||
src = graph.get_vertex(src_name)
|
||
dst = graph.get_vertex(dst_name)
|
||
if distance_map[src] + weight < distance_map[dst]:
|
||
distance_map[dst] = distance_map[src] + weight
|
||
predecessor_map[dst] = src
|
||
|
||
# Prüfdurchlauf: jede weitere Verbesserung zeigt einen negativen Zyklus
|
||
has_negative_cycle = False
|
||
for src_name, dst_name, weight in graph.all_edges():
|
||
src = graph.get_vertex(src_name)
|
||
dst = graph.get_vertex(dst_name)
|
||
if distance_map[src] + weight < distance_map[dst]:
|
||
has_negative_cycle = True
|
||
break
|
||
|
||
return distance_map, predecessor_map, has_negative_cycle
|
||
|
||
|
||
# --- a) + b) Basisgraph ---
|
||
|
||
g = AdjacencyListGraph()
|
||
for v in ['a', 'b', 'c', 'd', 'e']:
|
||
g.insert_vertex(v)
|
||
for src, dst, w in EDGES:
|
||
g.connect(src, dst, w)
|
||
|
||
dist, pred, neg_cycle = bellman_ford(g, 'a')
|
||
print(f"Negativer Zyklus: {neg_cycle}")
|
||
print("Kürzeste Distanzen:")
|
||
for name in ['a', 'b', 'c', 'd', 'e']:
|
||
v = g.get_vertex(name)
|
||
pfad = g.path(name, pred)
|
||
print(f" {name}: d={dist[v]}, Pfad: {' -> '.join(pfad)}")
|
||
|
||
# --- d) Komplexität ---
|
||
v_count = len(list(g.all_vertices()))
|
||
e_count = len(g.all_edges())
|
||
print(f"\n|V| = {v_count}, |E| = {e_count}")
|
||
|
||
# --- c) Negativer Zyklus ---
|
||
print("\n--- Mit negativem Zyklus (e -> b, Gewicht -8) ---")
|
||
g.connect('e', 'b', -8)
|
||
dist2, pred2, neg_cycle2 = bellman_ford(g, 'a')
|
||
print(f"Negativer Zyklus: {neg_cycle2}")
|
||
# Betroffener Zyklus: b -> c -> e -> b (1 + 4 + (-8) = -3 < 0)
|