რა არის წონიანი და მიმართული გრაფები და რა პრობლემებს მოდელირებენ ისინი?

Question

Accepted Answer

**მიმართულ** გრაფში (digraph) გრაფის წიბოებს აქვთ **მიმართულება** (`A → B` ≠ `B → A`). **წონიან** გრაფში თითოეული წიბო ატარებს **რიცხვით ღირებულებას** (მანძილი, დრო, სიმძლავრე). ორივეს კომბინირება მოდელირებს რეალურ სისტემებს, სადაც ურთიერთობები ცალმხრივი და ღირებულებით დატვირთულია.

## Representation

```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.
```

## What they model

| 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 |

## Key algorithms

| 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) |

## რატომ მნიშვნელოვანია

მიმართულება და წონა არის ის, რაც აბსტრაქტულ გრაფს აქცევს მარშრუტიზაციის, დაგეგმვისა და დამოკიდებულების პრობლემების ერთგულ მოდელში, რომელიც რეალურ აპლიკაციებს აძლევს ძალას.

ალგორითმის არჩევანი დამოკიდებულია ამ თვისებებზე — მაგალითად, უარყოფითი წონები გამორიცხავს დიჯკსტრას და მოითხოვს Bellman-Ford-ს.

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)