Co jsou vážené a orientované grafy a jaké problémy modelují?

Question

Accepted Answer

V **orientovaném** grafu (digraph) mají hrany **směr** (`A → B` ≠ `B → A`). V **váženém** grafu nese každá hrana **numerickou cenu** (vzdálenost, čas, kapacitu). Kombinace obou modeluje reálné systémy, kde jsou vztahy jednosměrné a mají cenu.

## Reprezentace

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

## Co modelují

| Doména | Vrcholy | Vážené orientované hrany |
|---|---|---|
| Mapy / GPS | křižovatky | jednosměrné silnice + doba cesty |
| Sítě | směrovače | linky + latence/šířka pásma |
| Plánování úkolů | úkoly | závislosti + doby trvání |
| Finance | měny | směnné kurzy |

## Klíčové algoritmy

| Cíl | Algoritmus | Složitost |
|---|---|---|
| Nejkratší cesta (nezáporné váhy) | Dijkstra | O((V+E) log V) |
| Nejkratší cesta (záporné hrany) | Bellman-Ford | O(VE) |
| Řazení se závislostmi | Topological sort | O(V+E) |
| Detekce cyklů / dosažitelnost | DFS | O(V+E) |

## Proč na tom záleží

Směr a váha jsou to, co transformuje abstraktní graf do věrného modelu problémů trasování, plánování a závislostí, které řídí reálné aplikace.

Volba algoritmu závisí na těchto vlastnostech — například záporné váhy vylučují Dijkstru a vyžadují Bellman-Ford.

Doména	Vrcholy	Vážené orientované hrany
Mapy / GPS	křižovatky	jednosměrné silnice + doba cesty
Sítě	směrovače	linky + latence/šířka pásma
Plánování úkolů	úkoly	závislosti + doby trvání
Finance	měny	směnné kurzy

Cíl	Algoritmus	Složitost
Nejkratší cesta (nezáporné váhy)	Dijkstra	O((V+E) log V)
Nejkratší cesta (záporné hrany)	Bellman-Ford	O(VE)
Řazení se závislostmi	Topological sort	O(V+E)
Detekce cyklů / dosažitelnost	DFS	O(V+E)