In einem gerichteten Graphen (digraph) haben Kanten eine Richtung (A → B ≠ B → A). In einem gewichteten Graphen trägt jede Kante (Entfernung, Zeit, Kapazität). Die Kombination beider modelliert reale Systeme, in denen Beziehungen einseitig sind und Kosten haben.
Weighted directed graph:
A --5--> B
A --2--> C
C --1--> B
Adjacency list with weights:
A: [(B,5), (C,2)]
B: []
C: [(B,1)]
graph = {
'A': [('B', 5), ('C', 2)], # directed, weighted edges
'B': [],
'C': [('B', 1)],
}
# Shortest A->B is A->C->B = 2 + 1 = 3, not the direct edge 5.
| Bereich | Knoten | Gewichtete gerichtete Kanten |
|---|---|---|
| Karten / GPS | Kreuzungen | Einbahnstraßen + Fahrtzeit |
| Netzwerke | Router | Links + Latenz/Bandbreite |
| Aufgabenplanung | Aufgaben | Abhängigkeiten + Dauer |
| Finanzen | Währungen | Wechselkurse |
| Ziel | Algorithmus | Komplexität |
|---|---|---|
| Kürzester Weg (nicht-negative Gewichte) | Dijkstra | O((V+E) log V) |
| Kürzester Weg (negative Kanten) | Bellman-Ford | O(VE) |
| Sortierung mit Abhängigkeiten | Topological sort | O(V+E) |
| Zykluserkennung / Erreichbarkeit | DFS | O(V+E) |
Richtung und Gewicht sind das, was einen abstrakten Graphen in ein treues Modell von Routing-, Planungs- und Abhängigkeitsproblemen verwandelt, die reale Anwendungen antreiben.
Die Wahl des Algorithmus hängt von diesen Eigenschaften ab — zum Beispiel schließen negative Gewichte Dijkstra aus und erfordern Bellman-Ford.