Fil-graff dirett (digraph), il-ħافiet għandhom direzzjoni (A → B ≠ B → A). Fil-graff ippesati, kull ħaff iġib ispiża numerika (distanza, ħin, kapaċità). Billi tnuddumedduha l-ishom jingħaqdu sistemi reali fejn ir-relazzjonijiet huma waħda-direzzjonali u għandhom ispiża.
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.
| Domain | Vertices | Weighted directed edges |
|---|---|---|
| Maps / GPS | intersections | one-way roads + travel time |
| Networks | routers | links + latency/bandwidth |
| Task scheduling | tasks | dependencies + durations |
| Finance | currencies | exchange rates |
| Goal | Algorithm | Complexity |
|---|---|---|
| Shortest path (non-negative weights) | Dijkstra | O((V+E) log V) |
| Shortest path (negative edges) | Bellman-Ford | O(VE) |
| Ordering with dependencies | Topological sort | O(V+E) |
| Detect cycles / reachability | DFS | O(V+E) |
Id-direzzjoni u l-ispiża huma dak li jinbdlu graff astratt f'mudell fiddewwa tal-prublemi ta' rotta, skehdija, u dipendenza li jidrivaw applikazzjonijiet reali.
Il-għażla tal-algoritmu tiddependi fuq dawn il-proprjetajiet — pereżempju, ispiziet negattivi jeskluduh Dijkstra u jeħtieġu Bellman-Ford.