In een gerichte graaf (digraph) hebben kanten een richting (A → B ≠ B → A). In een gewogen graaf draagt elke kant een (afstand, tijd, capaciteit). Het combineren van beide modelleert reële systemen waar relaties eenrichtings zijn en een kostprijs hebben.
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.
| Domein | Vertices | Gewogen gerichte kanten |
|---|---|---|
| Kaarten / GPS | kruispunten | eenrichtingswegen + reistijd |
| Netwerken | routers | verbindingen + latentie/bandbreedte |
| Taakplanning | taken | afhankelijkheden + duur |
| Financiën | valuta | wisselkoersen |
| Doel | Algoritme | Complexiteit |
|---|---|---|
| Kortste pad (niet-negatieve gewichten) | Dijkstra | O((V+E) log V) |
| Kortste pad (negatieve kanten) | Bellman-Ford | O(VE) |
| Ordening met afhankelijkheden | Topological sort | O(V+E) |
| Cycli detecteren / bereikbaarheid | DFS | O(V+E) |
Richting en gewicht zijn wat een abstracte graaf omzetten in een getrouw model van routing-, planning- en afhankelijkheidsproblemen die echte toepassingen aansturen.
De keuze van algoritme hangt af van deze eigenschappen — bijvoorbeeld sluiten negatieve gewichten Dijkstra uit en vereisen Bellman-Ford.