ایک سمتی گراف (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.
| ڈومین | عمودے | وزن والی سمتی کنارے |
|---|---|---|
| نقشے / GPS | سڑک کے منڈ | یک طرفہ سڑکیں + سفر کا وقت |
| نیٹ ورک | روٹرز | روابط + latency/bandwidth |
| کام کی منصوبہ بندی | کام | انحصار + مدت |
| مالیات | کرنسیز | شرح تبدیلی |
| مقصد | الگورتھم | پیچیدگی |
|---|---|---|
| سب سے قریب ترین راستہ (غیر منفی وزن) | Dijkstra | O((V+E) log V) |
| سب سے قریب ترین راستہ (منفی کنارے) | Bellman-Ford | O(VE) |
| انحصار کے ساتھ ترتیب | Topological sort | O(V+E) |
| سائیکلز کی شناخت / رسائی | DFS | O(V+E) |
سمت اور وزن ہی وہ چیزیں ہیں جو ایک تجریدی گراف کو routing، scheduling، اور انحصار کے مسائل کے قابلِ اعتماد ماڈل میں تبدیل کرتی ہیں جو حقیقی ایپلیکیشنز کو چلاتے ہیں۔
الگورتھم کا انتخاب ان خصوصیات پر منحصر ہے — مثال کے طور پر، منفی وزن Dijkstra کو مسترد کرتے ہیں اور Bellman-Ford کی ضرورت ہے۔