وزن والا اور سمتی گرافس کیا ہیں، اور وہ کون سے مسائل کا ماڈل بناتے ہیں؟

Question

Accepted Answer

ایک **سمتی** گراف (digraph) میں، کناروں کی **سمت** ہوتی ہے (`A → B` ≠ `B → A`)۔ ایک **وزن والے** گراف میں، ہر کنارے کے ساتھ ایک **عددی لاگت** ہوتی ہے (فاصلہ، وقت، صلاحیت)۔ دونوں کو ملا کر حقیقی نظاموں کا ماڈل بنتا ہے جہاں تعلقات یک طرفہ ہوں اور ان کی لاگت ہو۔

## نمائندگی

```text
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)]
```

```python
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 کی ضرورت ہے۔

ڈومین	عمودے	وزن والی سمتی کنارے
نقشے / GPS	سڑک کے منڈ	یک طرفہ سڑکیں + سفر کا وقت
نیٹ ورک	روٹرز	روابط + latency/bandwidth
کام کی منصوبہ بندی	کام	انحصار + مدت
مالیات	کرنسیز	شرح تبدیلی

مقصد	الگورتھم	پیچیدگی
سب سے قریب ترین راستہ (غیر منفی وزن)	Dijkstra	O((V+E) log V)
سب سے قریب ترین راستہ (منفی کنارے)	Bellman-Ford	O(VE)
انحصار کے ساتھ ترتیب	Topological sort	O(V+E)
سائیکلز کی شناخت / رسائی	DFS	O(V+E)