Penjelasan algoritma Dijkstra: cara kerja, kode, dan kompleksitas

Masalah yang diselesaikan algoritma Dijkstra

Breadth-first search menemukan jalur dengan edge paling sedikit, tetapi jalan, tautan jaringan, dan penerbangan punya panjang, biaya, atau delay yang berbeda-beda. Algoritma Dijkstra menyelesaikan masalah single-source shortest path pada graf berbobot semacam itu: dari sebuah node awal, cari total biaya termurah untuk mencapai setiap node lain, beserta jalur yang menghasilkannya.

Edsger W. Dijkstra menerbitkan algoritma ini pada 1959 dalam makalah "A note on two problems in connexion with graphs".

Ide dasar dengan kata-kata sederhana

1. Atur jarak node awal menjadi 0 dan jarak semua node lain menjadi tak hingga.
2. Pilih node belum final dengan jarak terkecil. Jaraknya kini final.
3. Relaksasi setiap edge keluar u → v dengan bobot w: jika dist[u] + w < dist[v], set dist[v] = dist[u] + w dan simpan u sebagai parent dari v.
4. Ulangi langkah 2 dan 3 sampai setiap node yang dapat dijangkau sudah final.

Mengapa jarak terkecil itu final? Setiap rute lain ke node tersebut harus melewati node yang jaraknya sudah paling tidak sebesar itu, dan dengan bobot non-negatif edge selanjutnya hanya bisa menambah biaya.

Contoh langkah demi langkah

Graf berarah dengan edge A→B (4), A→C (1), C→B (2), B→D (1), C→D (5), D→E (3). Mulai dari A.

B pertama kali mendapat jarak 4 dari edge langsung, lalu membaik menjadi 3 lewat C. Jalur terpendek ke E adalah A → C → B → D → E dengan total biaya 1 + 2 + 1 + 3 = 7.

Implementasi Python dengan heapq

Modul heapq Python menyediakan binary min-heap. Alih-alih operasi "decrease key", masukkan pasangan (distance, node) baru setiap kali jarak membaik dan lewati pasangan usang saat di-pop. Teknik ini disebut lazy deletion.

import heapq
def dijkstra(graph, start):
    dist = {start: 0}
    parent = {start: None}
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                      # outdated entry
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                parent[v] = u
                heapq.heappush(heap, (nd, v))
    return dist, parent
graph = {
    "A": [("B", 4), ("C", 1)], "B": [("D", 1)],
    "C": [("B", 2), ("D", 5)], "D": [("E", 3)], "E": [],
}
dist, parent = dijkstra(graph, "A")
print(dist)  # {'A': 0, 'B': 3, 'C': 1, 'D': 4, 'E': 7}

Untuk mendapatkan jalur ke satu target, ikuti tautan parent mundur ke node awal:

def path_to(parent, target):
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]
print(path_to(parent, "E"))  # ['A', 'C', 'B', 'D', 'E']

Jika Anda hanya butuh jarak ke satu target, Anda bisa berhenti begitu target itu keluar dari heap: jaraknya sudah final saat itu.

Kompleksitas waktu dan ruang

Ruangnya O(V + E) untuk graf, peta jarak dan parent, serta heap.

Varian dan kesalahan umum

• Melupakan pemeriksaan if d > dist[u]: continue memang tidak salah, tetapi membuat algoritma memproses entri usang dan bisa jauh lebih lambat.
• Memasukkan hanya node, bukan (distance, node), membuat urutan heap tidak bermakna.
• Jika node berupa objek yang tidak bisa dibandingkan, jarak yang sama membuat heapq membandingkan node dan memunculkan TypeError. Masukkan (distance, counter, node) dengan counter yang unik.
• A* search adalah Dijkstra dengan heuristik yang ditambahkan ke prioritas; ia menjelajah lebih sedikit node jika Anda punya estimasi jarak tersisa yang baik.
• Dijkstra dua arah berjalan dari node awal dan tujuan sekaligus, lalu berhenti saat kedua pencarian bertemu.

Kapan memakainya dan penggunaannya di dunia nyata

• Routing: protokol link-state seperti OSPF dan IS-IS menjalankan perhitungan shortest path first yang berbasis algoritma Dijkstra.
• Peta dan navigasi, tempat sistem produksi menambahkan preprocessing di atas pencarian ala Dijkstra.
• Soal wawancara: network delay time, cheapest flights (dengan batas transit), path with minimum effort pada grid, dan setiap soal "total biaya minimum" pada graf.