Veröffentlicht · wird verbessert
Algorithm
Kürzeste Wege mit Dijkstra, Bellman-Ford und Floyd-Warshall berechnen und minimale Spannbäume mit Kruskal und Prim aufbauen.
Beim Kürzeste-Wege-Problem sucht man in einem gewichteten Graphen den Weg mit der kleinsten Gewichtssumme zwischen zwei Knoten. Ein minimaler Spannbaum (MST) ist die günstigste Kantenmenge, die alle Knoten eines ungerichteten Graphen ohne Zyklus verbindet. Die zentralen Algorithmen dieses Themas sind Dijkstra, Bellman-Ford, Floyd-Warshall, 0-1-BFS, Kruskal und Prim.
Diese Algorithmen arbeiten in Navigationssystemen, in Routing-Protokollen wie OSPF und RIP, bei der Wegfindung in Spielen, bei der Planung von Leitungs- und Rohrnetzen und beim Clustering. In Coding-Interviews sind sie ein Klassiker, weil sie zeigen, ob man ein Problem als Graph modellieren und den passenden Algorithmus für die Gewichte wählen kann: negativ oder nicht, nur 0 und 1, dünn oder dicht besetzt.
Zuerst sollte man BFS und Prioritätswarteschlangen (Heaps) sicher beherrschen. Danach lernt man die Relaxation, die alle Kürzeste-Wege-Algorithmen gemeinsam haben, und verfolgt Dijkstra von Hand an einem kleinen Graphen. Anschließend klärt man, warum negative Kanten Bellman-Ford erfordern, implementiert Kruskal mit Union-Find und übt zum Schluss Aufgaben, in denen Dijkstra auf einem erweiterten Zustandsgraphen läuft.
Alle Kürzeste-Wege-Algorithmen beruhen auf der Relaxation, also der Prüfung, ob der Weg über u zu v kürzer ist. Sie unterscheiden sich nur in der Reihenfolge, in der sie Kanten relaxieren.
Bei nichtnegativen Gewichten entnimmt ein binärer Heap jeweils den nächstgelegenen Knoten und legt ihn fest; so entstehen alle Distanzen von einer Quelle in O((V + E) log V).
Bellman-Ford erlaubt negative Kanten und erkennt negative Zyklen; Floyd-Warshall berechnet die Distanzen zwischen allen Knotenpaaren in O(V^3).
Kruskal fügt Kanten von der leichtesten zur schwersten hinzu und verhindert Zyklen mit Union-Find; Prim lässt einen Baum über seine günstigste ausgehende Kante wachsen. Die Schnitteigenschaft macht beide korrekt.
heapq liefert (Distanz, Knoten)-Paare in aufsteigender Distanz; ein Paar, dessen Distanz größer als der gespeicherte Wert ist, ist veraltet und wird übersprungen. Verbessert sich die Distanz eines Nachbarn, wird sie aktualisiert und ein neues Paar eingefügt. python dijkstra.py gibt die kürzesten Distanzen ab A aus: {'A': 0, 'B': 3, 'C': 1, 'D': 4}.
dijkstra.py
import heapq
def dijkstra(graph, source):
dist = {source: 0}
heap = [(0, source)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # stale entry
for v, w in graph[u]:
nd = d + w
if nd < dist.get(v, float("inf")):
dist[v] = nd
heapq.heappush(heap, (nd, v))
return dist
graph = {
"A": [("B", 4), ("C", 1)],
"B": [("D", 1)],
"C": [("B", 2), ("D", 5)],
"D": [],
}
print(dijkstra(graph, "A")) # {'A': 0, 'B': 3, 'C': 1, 'D': 4}
python dijkstra.pySechs Kapitel führen dich von der Installation bis zu den Kernkonzepten von Kürzeste Wege und minimale Spannbäume.
Stelle Fragen, teile Erfahrungen und tausche Meinungen zu Kürzeste Wege und minimale Spannbäume aus.
Noch keine Diskussionen. Starte die erste.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.
Schreib den ersten Kommentar.