निर्देशित आलेखात (digraph), किनारांना दिशा असते (A → B ≠ B → A). वजनित आलेखात, प्रत्येक किनारे ला संख्यात्मक खर्च असतो (अंतर, वेळ, क्षमता). दोन्ही एकत्र केल्यास वास्तविक प्रणालींचे मॉडेल तयार होते जिथे संबंध एकमुखी आणि खर्चयुक्त असतात.
निर्देशित आलेखात (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.
| 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) |
दिशा आणि वजन हेच आहेत जे अमूर्त आलेखला मार्गदिशन, शेड्यूलिंग आणि अवलंबित्व समस्यांच्या विश्वस्त मॉडेलमध्ये रूपांतरित करतात जे वास्तविक अनुप्रयोगांना चालिते.
अल्गोरिदमची निवड या गुणधर्मांवर अवलंबून असते — उदाहरणार्थ, नकारात्मक वजन Dijkstra वगळते आणि Bellman-Ford आवश्यक होते.