Dalam graf berarah (digraph), tepi memiliki arah (A → B ≠ B → A). Dalam graf berbobot, setiap tepi membawa (jarak, waktu, kapasitas). Menggabungkan keduanya memodelkan sistem nyata di mana hubungan adalah satu arah dan memiliki biaya.
Dalam graf berarah (digraph), tepi memiliki arah (A → B ≠ B → A). Dalam graf berbobot, setiap tepi membawa (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.
Perpustakaan pertanyaan wawancara IT dengan jawaban mendetail — dari Junior hingga Senior.
Donasi