Într-un graf orientat (digraph), muchiile au o direcție (A → B ≠ B → A). Într-un graf ponderat, fiecare muchie poartă un (distanță, timp, capacitate). Combinarea ambelor modelează sisteme reale în care relațiile sunt într-o singură direcție și au un cost.
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.
| Domeniu | Vârfuri | Muchii ponderate orientate |
|---|---|---|
| Hărți / GPS | intersecții | drumuri într-o singură direcție + timp de călătorie |
| Rețele | routere | legături + latență/lățime de bandă |
| Planificare de sarcini | sarcini | dependențe + durate |
| Finanțe | valute | rate de schimb |
| Obiectiv | Algoritm | Complexitate |
|---|---|---|
| Cea mai scurtă cale (greutăți non-negative) | Dijkstra | O((V+E) log V) |
| Cea mai scurtă cale (muchii negative) | Bellman-Ford | O(VE) |
| Ordonare cu dependențe | Topological sort | O(V+E) |
| Detectare cicluri / accesibilitate | DFS | O(V+E) |
Direcția și greutatea sunt ceea ce transformă un graf abstract într-un model fidel al problemelor de rutare, planificare și dependență care alimentează aplicațiile reale.
Alegerea algoritmului depinde de aceste proprietăți — de exemplu, greutățile negative exclud Dijkstra și necesită Bellman-Ford.