I en rettet graf (digraph) har kanter en retning (A → B ≠ B → A). I en vægtet graf bærer hver kant en numerisk omkostning (afstand, tid, kapacitet). Kombinationen af begge modellerer reelle systemer, hvor relationer er envejede og har en omkostning.
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.
| Domæne | Knuder | Vægtede rettede kanter |
|---|---|---|
| Kort / GPS | krydsninger | envejsveje + rejsetid |
| Netværk | routere | links + latens/båndbredde |
| Opgaveplanlægning | opgaver | afhængigheder + varigheder |
| Finans | valutaer | vekselkurser |
| Mål | Algoritme | Kompleksitet |
|---|---|---|
| Korteste sti (ikke-negative vægte) | Dijkstra | O((V+E) log V) |
| Korteste sti (negative kanter) | Bellman-Ford | O(VE) |
| Ordning med afhængigheder | Topological sort | O(V+E) |
| Detektion af cyklusser / tilgængelighed | DFS | O(V+E) |
Retning og vægt er det, der omdanner en abstrakt graf til en troværdig model for routing-, planlægnings- og afhængighedsproblemer, der driver virkelige applikationer.
Valget af algoritme afhænger af disse egenskaber — for eksempel udelukker negative vægte Dijkstra og kræver Bellman-Ford.