Dalam graf berarah (digraph), tepi memiliki arah (A → B ≠ B → A). Dalam graf berbobot, setiap tepi membawa biaya numerik (jarak, waktu, kapasitas). Menggabungkan keduanya memodelkan sistem nyata di mana hubungan adalah satu arah dan memiliki biaya.
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.
| Domain | Simpul | Tepi berarah berbobot |
|---|---|---|
| Peta / GPS | persimpangan | jalan satu arah + waktu tempuh |
| Jaringan | router | link + latensi/bandwidth |
| Penjadwalan tugas | tugas | dependensi + durasi |
| Keuangan | mata uang | nilai tukar |
| Tujuan | Algoritma | Kompleksitas |
|---|---|---|
| Jalur terpendek (bobot non-negatif) | Dijkstra | O((V+E) log V) |
| Jalur terpendek (tepi negatif) | Bellman-Ford | O(VE) |
| Pengurutan dengan dependensi | Topological sort | O(V+E) |
| Deteksi siklus / reachability | DFS | O(V+E) |
Arah dan bobot adalah yang mengubah graf abstrak menjadi model setia dari permasalahan routing, penjadwalan, dan dependensi yang mendorong aplikasi nyata.
Pilihan algoritma bergantung pada properti ini — misalnya, bobot negatif mengeliminasi Dijkstra dan memerlukan Bellman-Ford.