Implementasi Algoritma Dijkstra: Mencari Rute Terpendek dalam Graf

Pendahuluan: Apa itu Algoritma Dijkstra?

Pernah bertanya-tanya bagaimana Google Maps bisa menemukan rute tercepat dari rumahmu ke kantor, bahkan saat ada kemacetan? Atau bagaimana paket data internet bisa melompat dari router ke router dan tiba di tujuan dengan jalur paling efisien? Di balik itu semua, ada algoritma yang dikembangkan oleh ilmuwan komputer Belanda, Edsger W. Dijkstra, pada tahun 1956.

Algoritma Dijkstra adalah algoritma greedy untuk mencari jalur terpendek dari satu titik sumber (source node) ke semua titik lain dalam sebuah graf berbobot (weighted graph) — asalkan semua bobotnya non-negatif.

Berbeda dengan algoritma sorting yang memproses elemen satu per satu secara linear, Dijkstra bekerja pada struktur graf dan secara cerdas menjelajahi jalur berdasarkan total bobot terendah yang terakumulasi. Ini adalah contoh nyata algoritma yang mengubah cara kita membangun sistem navigasi, jaringan komputer, hingga game AI.

Prasyarat: Memahami Graf dan Komponennya

Sebelum masuk ke implementasi, pastikan kamu paham konsep berikut:

Graf terdiri dari:

Node (vertex): titik-titik dalam graf (misal: kota, router, stasiun)
Edge: koneksi antar node
Weight (bobot): nilai pada setiap edge (misal: jarak, waktu, biaya)

    A ---4--- B
    |         |
    2         1
    |         |
    C ---3--- D

Dalam contoh di atas: A ke C berbobot 2, A ke B berbobot 4, B ke D berbobot 1, C ke D berbobot 3.

Graf bisa direpresentasikan dalam Python menggunakan adjacency list — struktur yang paling efisien untuk graf sparse (graf dengan sedikit edge):

# Representasi graf sebagai adjacency list
# Format: {node: [(tetangga, bobot), ...]}
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('D', 1)],
    'C': [('D', 3)],
    'D': []
}

Kenapa adjacency list? Karena lebih hemat memori dibanding adjacency matrix O(V²), terutama untuk graf dengan banyak node tapi sedikit koneksi. Kompleksitas ruangnya O(V + E) di mana V adalah jumlah vertex dan E adalah jumlah edge.

Logika dan Cara Kerja Algoritma Dijkstra

Dijkstra bekerja dengan prinsip sederhana: selalu proses node dengan total jarak terpendek yang belum diproses.

Langkah-langkahnya:

Inisialisasi: Set jarak ke semua node sebagai ∞ (tak terhingga), kecuali node sumber yang diset 0.
Priority Queue: Masukkan node sumber ke dalam min-heap (priority queue berdasarkan jarak minimum).
Loop Utama:
- Ambil node dengan jarak terkecil dari priority queue.
- Untuk setiap tetangga node tersebut, hitung jarak baru: jarak_sekarang + bobot_edge.
- Jika jarak baru lebih kecil dari jarak yang tersimpan, update jaraknya dan masukkan ke priority queue.
Selesai ketika priority queue kosong.

Mari kita trace secara manual untuk graf di atas, mulai dari node A:

Iterasi	Node Diproses	Jarak B	Jarak C	Jarak D
Awal	-	∞	∞	∞
1	A	4	2	∞
2	C (dist=2)	4	2	5
3	B (dist=4)	4	2	5
4	D (dist=5)	4	2	5

Hasil akhir: Rute terpendek A→D adalah A→C→D dengan total bobot 5, bukan A→B→D (4+1=5 — sama! tapi Dijkstra menemukan keduanya).

Implementasi Algoritma Dijkstra dengan Python

Implementasi Dasar

import heapq

def dijkstra(graph, source):
    """
    Mencari jarak terpendek dari source ke semua node lain.
    
    Args:
        graph: dict - adjacency list {node: [(tetangga, bobot), ...]}
        source: node awal
    
    Returns:
        distances: dict - jarak terpendek ke setiap node
        previous: dict - node sebelumnya dalam jalur terpendek
    """
    # Inisialisasi jarak semua node sebagai tak terhingga
    distances = {node: float('inf') for node in graph}
    distances[source] = 0
    
    # Menyimpan jalur (node sebelumnya)
    previous = {node: None for node in graph}
    
    # Min-heap: (jarak, node)
    priority_queue = [(0, source)]
    
    # Set untuk melacak node yang sudah diproses
    visited = set()
    
    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)
        
        # Skip jika sudah diproses (ada duplikat di heap)
        if current_node in visited:
            continue
        
        visited.add(current_node)
        
        # Eksplorasi tetangga
        for neighbor, weight in graph[current_node]:
            distance = current_dist + weight
            
            # Update jarak jika ditemukan jalur lebih pendek
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous[neighbor] = current_node
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances, previous


def reconstruct_path(previous, source, target):
    """Rekonstruksi jalur dari source ke target."""
    path = []
    current = target
    
    while current is not None:
        path.append(current)
        current = previous[current]
    
    path.reverse()
    
    # Jika jalur valid (dimulai dari source)
    if path[0] == source:
        return path
    return []  # Tidak ada jalur


# Contoh penggunaan
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('D', 1), ('E', 5)],
    'C': [('A', 2), ('D', 3), ('F', 6)],
    'D': [('B', 1), ('C', 3), ('E', 2)],
    'E': [('B', 5), ('D', 2)],
    'F': [('C', 6)]
}

distances, previous = dijkstra(graph, 'A')

print("Jarak terpendek dari A:")
for node, dist in sorted(distances.items()):
    path = reconstruct_path(previous, 'A', node)
    print(f"  A → {node}: {dist} | Jalur: {' → '.join(path)}")

Output:

Jarak terpendek dari A:
  A → A: 0 | Jalur: A
  A → B: 4 | Jalur: A → B
  A → C: 2 | Jalur: A → C
  A → D: 5 | Jalur: A → C → D
  A → E: 7 | Jalur: A → C → D → E
  A → F: 8 | Jalur: A → C → F

Analisis Kompleksitas

Dengan implementasi menggunakan binary heap (heapq):

Waktu: O((V + E) log V) — setiap node dan edge diproses sekali, dengan operasi heap O(log V)
Ruang: O(V) — menyimpan jarak dan priority queue

Untuk performa lebih tinggi pada graf sangat besar, bisa menggunakan Fibonacci heap yang menurunkan kompleksitas ke O(E + V log V), tapi implementasinya jauh lebih kompleks dan jarang diperlukan dalam praktik.

Versi dengan NetworkX (untuk Produksi)

Di lingkungan produksi, library networkx sudah menyediakan implementasi Dijkstra yang teroptimasi:

import networkx as nx

# Membuat graf berbobot
G = nx.Graph()
edges = [
    ('A', 'B', 4), ('A', 'C', 2),
    ('B', 'D', 1), ('C', 'D', 3),
    ('D', 'E', 2), ('B', 'E', 5),
    ('C', 'F', 6)
]
G.add_weighted_edges_from(edges)

# Mencari jalur terpendek
jalur = nx.dijkstra_path(G, 'A', 'E')
panjang = nx.dijkstra_path_length(G, 'A', 'E')

print(f"Jalur terpendek A → E: {' → '.join(jalur)}")
print(f"Total jarak: {panjang}")
# Output: Jalur terpendek A → E: A → C → D → E
# Total jarak: 7

Contoh Kasus Nyata: Dari GPS hingga Jaringan Komputer

1. Simulasi Navigasi Kota

# Simulasi peta kota dengan jarak antar tempat (dalam km)
peta_kota = {
    'Rumah':     [('Minimarket', 0.5), ('Halte_Bus', 1.2)],
    'Minimarket': [('Rumah', 0.5), ('Sekolah', 2.0), ('Apotek', 0.8)],
    'Halte_Bus': [('Rumah', 1.2), ('Kantor', 3.5), ('Mall', 4.0)],
    'Sekolah':   [('Minimarket', 2.0), ('Taman', 1.0)],
    'Apotek':    [('Minimarket', 0.8), ('Kantor', 2.5)],
    'Kantor':    [('Halte_Bus', 3.5), ('Apotek', 2.5), ('Mall', 1.5)],
    'Mall':      [('Halte_Bus', 4.0), ('Kantor', 1.5), ('Taman', 2.0)],
    'Taman':     [('Sekolah', 1.0), ('Mall', 2.0)]
}

distances, previous = dijkstra(peta_kota, 'Rumah')

print("=== Navigasi dari Rumah ===")
tujuan = 'Kantor'
jalur = reconstruct_path(previous, 'Rumah', tujuan)
print(f"Rute ke {tujuan}: {' → '.join(jalur)}")
print(f"Jarak total: {distances[tujuan]} km")
# Output:
# Rute ke Kantor: Rumah → Minimarket → Apotek → Kantor
# Jarak total: 3.8 km

2. Routing Jaringan Komputer

Protokol jaringan seperti OSPF (Open Shortest Path First) menggunakan Dijkstra untuk menentukan jalur terbaik pengiriman paket data. Setiap router menjadi node, dan bandwidth/latency menjadi bobot edge.

# Simulasi sederhana routing jaringan
jaringan = {
    'Router_A': [('Router_B', 10), ('Router_C', 5)],
    'Router_B': [('Router_A', 10), ('Router_D', 3), ('Router_E', 8)],
    'Router_C': [('Router_A', 5), ('Router_D', 7)],
    'Router_D': [('Router_B', 3), ('Router_C', 7), ('Server', 2)],
    'Router_E': [('Router_B', 8), ('Server', 4)],
    'Server':   [('Router_D', 2), ('Router_E', 4)]
}

distances, previous = dijkstra(jaringan, 'Router_A')
jalur_ke_server = reconstruct_path(previous, 'Router_A', 'Server')

print(f"Jalur paket ke Server: {' → '.join(jalur_ke_server)}")
print(f"Total latency: {distances['Server']} ms")
# Output:
# Jalur paket ke Server: Router_A → Router_B → Router_D → Server
# Total latency: 15 ms

Keterbatasan yang Perlu Diketahui

Dijkstra tidak bisa menangani bobot negatif. Jika kamu memiliki graf dengan bobot negatif (misalnya sistem reward/penalty), gunakan algoritma Bellman-Ford sebagai gantinya. Untuk mencari jalur terpendek antar semua pasangan node, pertimbangkan Floyd-Warshall.

Kesimpulan

Algoritma Dijkstra adalah salah satu algoritma fundamental dalam ilmu komputer yang wajib dikuasai setiap developer. Berikut poin-poin kunci yang perlu diingat:

Prinsip kerja: Greedy — selalu pilih node dengan jarak terkumulasi terkecil menggunakan priority queue (min-heap).
Kompleksitas: O((V + E) log V) dengan binary heap — efisien untuk graf berukuran sedang hingga besar.
Syarat utama: Hanya bekerja untuk bobot non-negatif.
Aplikasi nyata: GPS/navigasi, routing jaringan (OSPF), game pathfinding (A* adalah evolusi dari Dijkstra), analisis jaringan sosial.
Implementasi Python: Gunakan heapq untuk priority queue, atau networkx untuk kebutuhan produksi.

Memahami Dijkstra bukan hanya tentang hafal kodenya — tapi tentang melatih cara berpikir dalam menyelesaikan masalah optimasi berbasis graf. Dari sini, kamu bisa melanjutkan ke algoritma yang lebih canggih seperti A* (yang menambahkan heuristic ke Dijkstra) atau Bellman-Ford untuk menangani kasus dengan bobot negatif.