I en riktad graf (digraf) har kanter en riktning (A → B ≠ B → A). I en vägrad graf bär varje kant en numerisk kostnad (avstånd, tid, kapacitet). Kombinationen modellerar verkliga system där relationer är enkelriktade och har en kostnad.
I en riktad graf (digraf) har kanter en riktning (A → B ≠ B → A). I en vägrad graf bär varje kant en numerisk kostnad (avstånd, tid, kapacitet). Kombinationen modellerar verkliga system där relationer är enkelriktade och har en kostnad.
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än | Noder | Vägda riktade kanter |
|---|---|---|
| Kartor / GPS | korsningar | enkelriktade vägar + restid |
| Nätverk | routrar | länkar + latens/bandbredd |
| Aktivitetsplanering | uppgifter | beroenden + varaktigheter |
| Finans | valutor | växelkurser |
| Mål | Algoritm | Komplexitet |
|---|---|---|
| Kortaste vägen (icke-negativa vikter) | Dijkstra | O((V+E) log V) |
| Kortaste vägen (negativa kanter) | Bellman-Ford | O(VE) |
| Ordning med beroenden | Topologisk sortering | O(V+E) |
| Detektera cykler / nåbarhet | DFS | O(V+E) |
Riktning och vikt är vad som förvandlar en abstrakt graf till en trovärdig modell av routing-, schemaläggnings- och beroendeproblem som driver verkliga applikationer.
Valet av algoritm beror på dessa egenskaper — till exempel utesluter negativa vikter Dijkstra och kräver Bellman-Ford.