Algorithmus

Kürzeste Wege und minimale Spannbäume

Kürzeste Wege mit Dijkstra, Bellman-Ford und Floyd-Warshall berechnen und minimale Spannbäume mit Kruskal und Prim aufbauen.

Anleitung starten Diskussionen

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.

Besonderheiten

Relaxation

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.

Dijkstra mit Heap

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).

Negative Kanten und alle Paare

Bellman-Ford erlaubt negative Kanten und erkennt negative Zyklen; Floyd-Warshall berechnet die Distanzen zwischen allen Knotenpaaren in O(V^3).

Gierige MST-Verfahren

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.

Einsatzgebiete

Routenplanung und Navigation
Routing-Protokolle (OSPF, RIP)
Netzplanung für Kabel und Rohre
Wegfindung in Spielen und Clustering

Referenzimplementierung

Dijkstra mit Heap

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.py

Schritt-für-Schritt-Anleitung

Sechs Kapitel führen dich von der Installation bis zu den Kernkonzepten von Kürzeste Wege und minimale Spannbäume.

Offizielle Dokumentation und Ressourcen

Diskussionen

Diskussion starten

Stelle Fragen, teile Erfahrungen und tausche Meinungen zu Kürzeste Wege und minimale Spannbäume aus.

Noch keine Diskussionen. Starte die erste.

0 Kommentare

Kürzeste Wege und minimale Spannbäume

Kürzeste Wege mit Dijkstra, Bellman-Ford und Floyd-Warshall berechnen und minimale Spannbäume mit Kruskal und Prim aufbauen.

Besonderheiten

Relaxation

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.

Dijkstra mit Heap

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).

Negative Kanten und alle Paare

Bellman-Ford erlaubt negative Kanten und erkennt negative Zyklen; Floyd-Warshall berechnet die Distanzen zwischen allen Knotenpaaren in O(V^3).

Gierige MST-Verfahren

Referenzimplementierung

Dijkstra mit Heap

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.py