Kürzeste-Wege-Algorithmen beherrschen:
Dijkstra, Bellman-Ford und Floyd-Warshall

1. Einführung in das Problem des kürzesten Weges

Im weiten Feld der Informatik sind nur wenige Probleme so universell anwendbar wie das "Problem des kürzesten Weges". Egal, ob es sich um Google Maps handelt, das bei starkem Verkehr die schnellste Route nach Hause berechnet, oder um einen Internet-Router, der bestimmt, wie ein Datenpaket weitergeleitet werden soll, die zugrunde liegende Mathematik ist identisch.

Im Kern fragt das Problem: Gegeben sei ein Graph aus Knotenpunkten (Orten) und Kanten (verbindenden Straßen), wobei jeder Kante eine "Gewichtung" (Entfernung, Zeit oder Kosten) zugewiesen ist, was ist der Pfad von einem Startknoten zu einem Zielknoten, der das Gesamtgewicht minimiert?

Obwohl dieses Problem einfach klingen mag, ändert sich die Natur des Graphen (ob er gerichtet ist, negative Gewichte enthält oder Zyklen aufweist), was drastisch unterschiedliche algorithmische Ansätze erfordert. In diesem Leitfaden werden wir die drei Säulen der Kürzeste-Wege-Algorithmen aufschlüsseln: Dijkstra, Bellman-Ford und Floyd-Warshall.

2. Dijkstras Algorithmus: Das gierige Arbeitstier

Konzipiert von dem legendären niederländischen Informatiker Edsger W. Dijkstra im Jahr 1956, ist dieser Algorithmus der unbestrittene König des Routings in Computernetzwerken und bei der Kartennavigation.

Die Strategie: Dijkstras Algorithmus verwendet einen "Greedy"-Ansatz (gierigen Ansatz). Er wählt immer den unbesuchten Knoten aus, der der Quelle am nächsten ist, erkundet seine Nachbarn und aktualisiert ihre Entfernungen. Sobald ein Knoten verarbeitet ist, ist er dauerhaft erledigt.

Die Mechanik

Um effizient den Knoten mit der derzeit kleinsten bekannten Entfernung zu finden, stützt sich Dijkstra stark auf eine Prioritätswarteschlange (Priority Queue) (oft implementiert als Min-Heap).

1. Weisen Sie jedem Knoten einen anfänglichen Entfernungs-Wert zu: 0 für den Startknoten und Unendlich für alle anderen.
2. Fügen Sie den Startknoten in die Prioritätswarteschlange ein.
3. Solange die Warteschlange nicht leer ist, entnehmen Sie den Knoten mit der kleinsten Entfernung.
4. Untersuchen Sie alle unbesuchten Nachbarn dieses Knotens.
5. Berechnen Sie die Entfernung von der Quelle zu jedem Nachbarn über den aktuellen Knoten.
6. Wenn diese neu berechnete Entfernung kleiner ist als die bekannte Entfernung des Nachbarn, aktualisieren Sie die Entfernung des Nachbarn und schieben Sie ihn in die Prioritätswarteschlange.

Implementierung in Python

import heapq

def dijkstra(graph, start):
    # Initialisiere Entfernungen mit Unendlich
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    
    # Die Prioritätswarteschlange speichert Tupel von (Entfernung, Knoten)
    pq = [(0, start)]
    
    while pq:
        # Den Knoten mit der geringsten Entfernung holen
        current_distance, current_vertex = heapq.heappop(pq)

        # Einen Knoten ignorieren, wenn wir bereits einen besseren Weg gefunden haben
        if current_distance > distances[current_vertex]:
            continue

        # Nachbarn überprüfen
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            # Wenn ein kürzerer Weg gefunden wurde, aktualisieren
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

Der fatale Fehler: Negative Gewichte

Dijkstras gierige Natur macht ihn unglaublich schnell (O((V + E) log V)). Dieser Geiz hat jedoch einen fatalen Fehler: Er geht davon aus, dass das Hinzufügen einer Kante zu einem Pfad den Pfad niemals kürzer machen kann. Folglich schlägt Dijkstra kläglich fehl, wenn der Graph Kanten mit negativen Gewichten enthält, da ein einmal "erledigter" Knoten nie wieder überdacht wird, selbst wenn eine versteckte negative Kante ihn später billiger machen würde.

3. Bellman-Ford Algorithmus: Umgang mit dem Negativen

Wenn Sie nicht garantieren können, dass alle Kantengewichte positiv sind (z.B. bei der Modellierung von Finanztransaktionen, wo einige Transaktionen Gewinn statt Kosten bringen), kommt der Bellman-Ford-Algorithmus ins Spiel. Während Dijkstra ein gieriger Algorithmus ist, verwendet Bellman-Ford einen Dynamic Programming Ansatz.

Die Strategie: Anstatt clever den nächstgelegenen Knoten auszuwählen, wählt Bellman-Ford einen Vorschlaghammer-Ansatz: Er "entspannt" (aktualisiert die Entfernungen) einfach jede einzelne Kante im Graphen. Und er tut dies V - 1 mal.

Warum V - 1 Iterationen?

Der längste mögliche Pfad in einem Graphen ohne Zyklus kann höchstens V - 1 Kanten haben (wobei V die Anzahl der Knoten ist). Indem alle Kanten V - 1 mal entspannt werden, garantiert der Algorithmus, dass sich die Entfernungen auf ihre absolut kürzesten Werte einpendeln, selbst wenn der Weg durch ein Labyrinth von negativen Kanten führen muss.

Erkennung negativer Zyklen

Die größte Superkraft von Bellman-Ford ist seine Fähigkeit, negative Gewichtszyklen zu erkennen. Wenn Sie nach V - 1 Iterationen die Kanten noch einmal entspannen und sich eine Entfernung immer noch verringert, bedeutet das, dass der Graph einen negativen Zyklus aufweist (eine Endlosschleife, die die Kosten für immer verringert, wie eine unendliche Geld-Arbitrage). In solchen Fällen ist der "kürzeste Weg" mathematisch undefiniert.

Implementierung in Python

def bellman_ford(graph, V, start):
    # Initialisiere Entfernungen
    distances = {vertex: float('infinity') for vertex in range(V)}
    distances[start] = 0

    # Entspanne alle Kanten V - 1 mal
    for _ in range(V - 1):
        for u, v, w in graph:
            if distances[u] != float('infinity') and distances[u] + w < distances[v]:
                distances[v] = distances[u] + w

    # Ein V-tes Mal ausführen, um nach negativen Zyklen zu suchen
    for u, v, w in graph:
        if distances[u] != float('infinity') and distances[u] + w < distances[v]:
            print("Graph enthält einen Zyklus mit negativem Gewicht!")
            return None

    return distances

4. Floyd-Warshall Algorithmus: Die All-Pairs Lösung

Sowohl Dijkstra als auch Bellman-Ford sind Single-Source Algorithmen für den kürzesten Weg (sie finden den Weg von einem Startpunkt zu allen anderen Punkten). Was ist, wenn Sie den kürzesten Weg von jedem Knoten zu jedem anderen Knoten gleichzeitig wissen müssen?

Der Floyd-Warshall-Algorithmus bietet eine unglaublich elegante Alternative. Er ist ein weiterer Dynamic Programming Ansatz, arbeitet aber auf der gesamten Adjazenzmatrix des Graphen.

Die Strategie: Floyd-Warshall prüft systematisch, ob die Route über einen Zwischenknoten k kürzer ist als die derzeit bekannte Route von Knoten i nach Knoten j.

Die Eleganz dieses Algorithmus liegt in seinen bemerkenswert einfachen drei verschachtelten Schleifen. Er ist extrem einfach zu implementieren und hervorragend für dichte Graphen geeignet.

Implementierung in Python

def floyd_warshall(graph_matrix, V):
    # Eine Kopie der Graphmatrix erstellen, um die Entfernungen zu speichern
    dist = [[float('infinity') for _ in range(V)] for _ in range(V)]
    
    # Basisfälle einrichten
    for i in range(V):
        dist[i][i] = 0
    for u in range(V):
        for v in range(V):
            if graph_matrix[u][v] != 0:
                dist[u][v] = graph_matrix[u][v]

    # Der Kern-Algorithmus
    for k in range(V):
        for i in range(V):
            for j in range(V):
                # Wenn der Pfad über 'k' kürzer ist, aktualisiere den Pfad
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
                
    return dist

5. Umfassender Vergleich