निर्देशित ग्राफ (digraph) मा, किनारहरूको दिशा हुन्छ (A → B ≠ B → 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.
| क्षेत्र | शीर्षहरू | भारित निर्देशित किनारहरू |
|---|---|---|
| नक्शा / GPS | चौराहाहरू | एकतर्फी सडकहरू + यात्रा समय |
| नेटवर्कहरू | राउटरहरू | लिङ्कहरू + विलम्बता/ब्यान्डविड्थ |
| कार्य समय निर्धारण | कार्यहरू | निर्भरताहरू + अवधि |
| वित्त | मुद्राहरू | विनिमय दरहरू |
| लक्ष्य | एल्गोरिदम | जटिलता |
|---|---|---|
| सबैभन्दा छोटो पथ (गैर-नकारात्मक भार) | Dijkstra | O((V+E) log V) |
| सबैभन्दा छोटो पथ (नकारात्मक किनारहरू) | Bellman-Ford | O(VE) |
| निर्भरताहरू सहित क्रम | Topological sort | O(V+E) |
| चक्र पहिचान / पहुँच | DFS | O(V+E) |
दिशा र भार एक अमूर्त ग्राफलाई रूटिङ, समय निर्धारण, र निर्भरता समस्याहरूको वास्तविक मडेलमा परिणत गर्छन् जसले वास्तविक अनुप्रयोगहरूलाई सञ्चालन गर्छ।
एल्गोरिदमको छनोट यी गुणहरूमा निर्भर गर्छ — उदाहरणका लागि, नकारात्मक भारहरूले Dijkstra लाई बाहिर राख्छ र Bellman-Ford आवश्यक गर्छ।