Algoritma Dijkstra: Pengertian, Cara Kerja, dan Contohnya

Dalam dunia ilmu komputer, pencarian jalur terpendek adalah masalah klasik yang sering muncul di berbagai bidang, mulai dari perencanaan rute perjalanan, manajemen jaringan komputer, hingga perancangan game. Salah satu algoritma paling terkenal untuk menyelesaikan masalah ini adalah Algoritma Dijkstra.

Diperkenalkan pada tahun 1956 oleh ilmuwan komputer asal Belanda, Edsger W. Dijkstra, algoritma ini dirancang untuk menghitung jalur terpendek dari satu titik (disebut source) ke semua titik lain dalam sebuah graf berbobot non-negatif.
Walaupun sederhana, Dijkstra tetap menjadi algoritma yang sangat relevan di dunia modern, termasuk di aplikasi seperti Google Maps, sistem navigasi kendaraan, hingga protokol routing internet.

Dasar Teori: Graf, Node, Edge, dan Bobot

Sebelum memahami cara kerja Dijkstra, penting untuk mengerti konsep dasar graf.

Node (Simpul/Vertex): Titik dalam graf, mewakili lokasi atau entitas.
Edge (Sisi): Garis yang menghubungkan dua node, mewakili hubungan atau jalur.
Bobot (Weight): Nilai numerik pada setiap edge yang menunjukkan biaya perjalanan, seperti jarak, waktu, atau biaya energi.
Graf Berarah: Setiap edge punya arah tertentu (misalnya dari A ke B).
Graf Tak Berarah: Edge bisa dilalui dua arah.
Graf Berbobot Non-Negatif: Semua bobot bernilai nol atau positif — ini syarat penting untuk Dijkstra.

Contoh graf sederhana:

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

Pengertian Algoritma Dijkstra

Algoritma Dijkstra adalah metode untuk mencari jalur terpendek dari satu node awal menuju node lain di graf dengan bobot non-negatif.
Prinsipnya adalah mencari jalur dengan biaya total terkecil secara bertahap, mulai dari node awal, lalu memperluas ke tetangga terdekat yang memiliki jarak minimum yang belum dikunjungi.

Cara Kerja Algoritma Dijkstra

Langkah-langkahnya sebagai berikut:

Inisialisasi
- Tetapkan jarak awal dari source ke dirinya sendiri = 0.
- Semua node lain diberi jarak awal = ∞ (tak terhingga).
- Tandai semua node sebagai “belum dikunjungi”.
Pilih Node dengan Jarak Minimum
- Pilih node yang belum dikunjungi dan memiliki jarak terkecil.
Perbarui Jarak Tetangga
- Untuk setiap tetangga node tersebut, hitung jarak baru: jarak_baru = jarak_node_saat_ini + bobot_edge Jika jarak_baru lebih kecil dari jarak sebelumnya, perbarui nilainya.
Tandai sebagai Dikunjungi
- Setelah semua tetangga diperbarui, tandai node sebagai “dikunjungi”.
- Node yang sudah dikunjungi tidak akan diperiksa lagi.
Ulangi
- Ulangi langkah 2–4 sampai semua node dikunjungi atau jarak ke node tujuan ditemukan.

Contoh Perhitungan Manual

Misal graf tak berarah berikut:

    (A)
   /   \
  4     2
 /       \
(B)---5---(C)
  \       /
   1     8
    \   /
     (D)

Langkah-langkah:

Inisialisasi: Jarak awal: A=0, B=∞, C=∞, D=∞
Iterasi 1:
- Pilih A (jarak 0).
- Perbarui B = 0+4=4, C=0+2=2.
A=0, B=4, C=2, D=∞
Iterasi 2:
- Pilih C (jarak 2).
- Perbarui D melalui C: 2+8=10 → D=10.
- Perbarui B melalui C: 2+5=7 (tidak lebih baik dari 4, abaikan).
A=0, B=4, C=2, D=10
Iterasi 3:
- Pilih B (jarak 4).
- Perbarui D: 4+1=5 → lebih baik dari 10 → D=5.
A=0, B=4, C=2, D=5
Iterasi 4:
- Pilih D (jarak 5). Tidak ada pembaruan.
- Selesai.

Hasil jalur terpendek dari A:

A ke B: 4
A ke C: 2
A ke D: 5

Pseudocode Algoritma Dijkstra

function Dijkstra(Graph, source):
    buat set jarak[node] = ∞ untuk semua node
    jarak[source] = 0
    buat set belum_dikunjungi = semua node

    while belum_dikunjungi tidak kosong:
        current = node dengan jarak terkecil di belum_dikunjungi
        hapus current dari belum_dikunjungi

        for setiap tetangga dari current:
            jarak_baru = jarak[current] + bobot_edge(current, tetangga)
            if jarak_baru < jarak[tetangga]:
                jarak[tetangga] = jarak_baru

    return jarak

Implementasi Python

import heapq

def dijkstra(graph, start):
    jarak = {node: float('inf') for node in graph}
    jarak[start] = 0
    pq = [(0, start)]

    while pq:
        dist, node = heapq.heappop(pq)
        if dist > jarak[node]:
            continue
        for tetangga, bobot in graph[node].items():
            jarak_baru = dist + bobot
            if jarak_baru < jarak[tetangga]:
                jarak[tetangga] = jarak_baru
                heapq.heappush(pq, (jarak_baru, tetangga))
    return jarak

# Contoh graf
graf = {
    'A': {'B': 4, 'C': 2},
    'B': {'A': 4, 'C': 5, 'D': 1},
    'C': {'A': 2, 'B': 5, 'D': 8},
    'D': {'B': 1, 'C': 8}
}

print(dijkstra(graf, 'A'))

Output:

{'A': 0, 'B': 4, 'C': 2, 'D': 5}

Optimisasi Algoritma Dijkstra

Priority Queue (Heap): Menggunakan heapq di Python untuk mempercepat pemilihan node dengan jarak minimum.
Adjacency List: Representasi graf yang hemat memori, cocok untuk graf jarang (sparse graph).
Hentikan lebih awal: Jika hanya butuh jalur ke satu tujuan, bisa berhenti ketika tujuan ditemukan.

Penerapan di Dunia Nyata

Navigasi Transportasi
- Google Maps, Waze, dan GPS mobil memanfaatkan prinsip Dijkstra untuk mencari rute tercepat.

Routing Jaringan Komputer
- Protokol seperti OSPF (Open Shortest Path First) menggunakan algoritma ini untuk menentukan rute data.
Game Development
- AI musuh mencari jalur di peta game.
Logistik dan Distribusi
- Perusahaan kurir menghitung rute optimal untuk pengiriman barang.

Kelebihan dan Kekurangan

Kelebihan

Menjamin jalur terpendek ditemukan (optimal) pada graf dengan bobot non-negatif.
Mudah diimplementasikan.
Cocok untuk graf ukuran kecil hingga menengah.

Kekurangan

Tidak bisa digunakan untuk bobot negatif (gunakan Bellman-Ford untuk itu).
Untuk graf yang sangat besar, performa bisa melambat tanpa optimisasi.
Hanya menghitung jarak terpendek, tidak mempertimbangkan faktor dinamis seperti perubahan kondisi jalan secara real-time (kecuali dikombinasikan dengan data terkini).

Perbandingan dengan Algoritma Lain

Algoritma	Bobot Negatif	Kompleksitas	Kelebihan
Dijkstra	Tidak	O(E log V)	Cepat untuk bobot non-negatif
Bellman-Ford	Ya	O(VE)	Menangani bobot negatif
A*	Tidak	O(E log V)	Lebih cepat jika ada heuristik

FAQ

Q: Apakah Dijkstra bisa digunakan untuk graf berbobot negatif?
A: Tidak. Gunakan algoritma Bellman-Ford untuk kasus tersebut.

Q: Apakah Dijkstra menghitung jalur terpendek ke semua node sekaligus?
A: Ya, secara default. Tapi bisa dihentikan lebih awal jika hanya butuh jalur ke satu tujuan.

Q: Apakah bisa digunakan untuk graf dinamis?
A: Bisa, tapi perlu dijalankan ulang atau dimodifikasi setiap ada perubahan pada graf.

Kesimpulan

Algoritma Dijkstra adalah salah satu algoritma paling fundamental untuk pencarian jalur terpendek dalam graf berbobot non-negatif.
Dengan prinsip sederhana namun efektif, Dijkstra menjadi tulang punggung berbagai teknologi modern, mulai dari navigasi peta, routing internet, hingga perencanaan logistik.

Memahami algoritma ini bukan hanya penting untuk mahasiswa atau programmer, tetapi juga untuk siapa pun yang bekerja dengan sistem yang membutuhkan optimisasi jalur. Dengan menguasai konsep, langkah perhitungan, hingga implementasinya, kita bisa mengadaptasikan Dijkstra ke berbagai masalah dunia nyata.

Ingin Membuat Aplikasi Website atau Android?

Kami, PT EduTech Media Group, siap membantu Anda mengembangkan solusi digital yang andal dan berkualitas tinggi. Dengan tim developer berpengalaman, kami menawarkan layanan pengembangan aplikasi web dan mobile yang sesuai dengan kebutuhan bisnis Anda.

Post Views: 17