एक directed graph (digraph) में, edges की एक दिशा होती है (A → B ≠ B → A)। एक weighted graph में, प्रत्येक edge एक (distance, time, capacity) रखता है। दोनों को मिलाकर वास्तविक systems को मॉडल किया जाता है जहाँ संबंध एकतरफा होते हैं और जिनकी एक लागत होती है।
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) |
दिशा और weight ही वे चीज़ें हैं जो एक अमूर्त graph को routing, scheduling और dependency समस्याओं का एक विश्वसनीय मॉडल बनाती हैं जो वास्तविक अनुप्रयोगों को चलाती हैं।
algorithm का चुनाव इन्हीं गुणों पर निर्भर करता है — उदाहरण के लिए, negative weights Dijkstra को बाहर कर देते हैं और Bellman-Ford की आवश्यकता होती है।