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.
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.
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.
| 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) |
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.
Knihovna IT otázek k pohovoru s podrobnými odpověďmi — od Junior po Senior.
Přispět