Az irányított gráfban (digraph) az élek irányítottak (A → B ≠ B → A). A súlyozott gráfban minden élhez tartozik egy (távolság, idő, kapacitás). Mindkettő kombinálásával olyan valós rendszereket modellezhetünk, ahol az relációk egyirányúak és költségük van.
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.
| Terület | Csúcsok | Súlyozott irányított élek |
|---|---|---|
| Térképek / GPS | kereszteződések | egyirányú utak + utazási idő |
| Hálózatok | routerek | linkek + latencia/sávszélesség |
| Feladatütemezés | feladatok | függőségek + időtartamok |
| Pénzügy | valuták | árfolyamok |
| Cél | Algoritmus | Komplexitás |
|---|---|---|
| Legrövidebb út (nem-negatív súlyok) | Dijkstra | O((V+E) log V) |
| Legrövidebb út (negatív élek) | Bellman-Ford | O(VE) |
| Rendezés függőségekkel | Topológiai rendezés | O(V+E) |
| Ciklusdetektálás / elérhetőség | DFS | O(V+E) |
Az irányítás és a súly azok, amelyek egy absztrakt gráfot a routing, ütemezés és függőség problémák hiteles modelljévé alakítanak, amelyek a valós alkalmazásokat hajtják.
Az algoritmus kiválasztása ezektől a tulajdonságoktól függ — például a negatív súlyok kizárják a Dijkstrát, és a Bellman-Ford algoritmust követelik meg.