Yönlendirilmiş bir grafikte (digraf), kenarların yönü vardır (A → B ≠ B → A). Ağırlıklı bir grafikte, her kenarın sayısal bir maliyeti (mesafe, zaman, kapasite) vardır. Her ikisini birleştirmek, ilişkilerin tek yönlü ve bir maliyete sahip olduğu gerçek sistemleri modeller.
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.
| Alan | Köşeler | Ağırlıklı yönlendirilmiş kenarlar |
|---|---|---|
| Haritalar / GPS | kesişimler | tek yönlü yollar + seyahat süresi |
| Ağlar | yönlendiriciler | bağlantılar + gecikme/bant genişliği |
| Görev planlama | görevler | bağımlılıklar + süreler |
| Finans | para birimleri | döviz kurları |
| Hedef | Algoritma | Karmaşıklık |
|---|---|---|
| En kısa yol (negatif olmayan ağırlıklar) | Dijkstra | O((V+E) log V) |
| En kısa yol (negatif kenarlar) | Bellman-Ford | O(VE) |
| Bağımlılıklarla sıralama | Topolojik sıralama | O(V+E) |
| Döngüleri algıla / ulaşılabilirlik | DFS | O(V+E) |
Yön ve ağırlık, soyut bir grafiği gerçek uygulamaları yönlendiren yönlendirme, planlama ve bağımlılık problemlerinin güvenilir bir modeline dönüştüren şeydir.
Algoritma seçimi bu özelliklere bağlıdır — örneğin, negatif ağırlıklar Dijkstra'yı dışlar ve Bellman-Ford gerektirir.