I en rettet graf (digraph) har kanter en retning (A → B ≠ B → A). I en vektet graf har hver kant en numerisk kostnad (avstand, tid, kapasitet). Kombinasjonen av begge modellerer reelle systemer der relasjoner er enveis og har en kostnad.
I en rettet graf (digraph) har kanter en retning (A → B ≠ B → A). I en vektet graf har hver kant en numerisk kostnad (avstand, tid, kapasitet). Kombinasjonen av begge modellerer reelle systemer der relasjoner er enveis og 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.
| Domene | Noder | Vektede rettede kanter |
|---|---|---|
| Kart / GPS | veikryss | enveisveier + reisetid |
| Nettverk | rutere | koblinger + latens/båndbredde |
| Oppgaveplanning | oppgaver | avhengigheter + varigheter |
| Finans | valutaer | valutakurser |
| Mål | Algoritme | Kompleksitet |
|---|---|---|
| Korteste vei (ikke-negative vekter) | Dijkstra | O((V+E) log V) |
| Korteste vei (negative kanter) | Bellman-Ford | O(VE) |
| Ordning med avhengigheter | Topological sort | O(V+E) |
| Detektere sykler / nåbarhet | DFS | O(V+E) |
Retning og vekt er hva som forvandler en abstrakt graf til en trofast modell av routing-, planleggings- og avhengighetsproblemer som driver reelle applikasjoner.
Valgmulighetene for algoritmen avhenger av disse egenskapene — for eksempel utelukker negative vekter Dijkstra og krever Bellman-Ford.