DWI WAHYU ILAHI ANGKA

Apa itu Algoritma Dijkstra?

Algoritma Dijkstra adalah sebuah algoritma yang digunakan untuk menemukan jalur terpendek dari satu titik (disebut node sumber) ke semua titik lainnya dalam sebuah grafik berbobot (weighted graph). Grafik berbobot adalah grafik di mana setiap sisi (edge) memiliki nilai numerik, yang biasanya merepresentasikan jarak, biaya, atau waktu. Algoritma ini pertama kali ditemukan oleh ilmuwan komputer Belanda, Edsger W. Dijkstra, pada tahun 1956 dan diterbitkan pada tahun 1959.

Algoritma ini sangat berguna dalam berbagai skenario, seperti:

Sistem navigasi GPS: Menemukan rute terpendek antar lokasi.
Perutean jaringan: Menentukan jalur data yang paling efisien.
Analisis peta: Mencari jalur terpendek di antara kota-kota.
Permainan: Menentukan jalur terpendek untuk karakter dalam game.

Cara Kerja Algoritma Dijkstra

Algoritma Dijkstra bekerja dengan cara yang mirip dengan "membengkak" dari titik sumber, secara bertahap menemukan jalur terpendek ke setiap node. Berikut adalah langkah-langkah intinya:

Inisialisasi:
- Tetapkan jarak ke node sumber adalah 0 dan jarak ke semua node lainnya adalah tak terbatas (infinity).
- Buat sebuah set untuk node yang sudah "dikunjungi" (sudah menemukan jalur terpendeknya) dan set untuk node yang "belum dikunjungi".
Iterasi:
- Pilih node dari set "belum dikunjungi" yang memiliki jarak terpendek dari node sumber.
- Tandai node yang dipilih ini sebagai "dikunjungi".
- Untuk setiap tetangga dari node yang baru saja dikunjungi:
  - Hitung jarak sementara dari node sumber ke tetangga ini melalui node yang baru saja dikunjungi.
  - Jika jarak sementara ini lebih pendek dari jarak yang sudah ada untuk tetangga tersebut, perbarui jarak tetangga tersebut.
Pengulangan:
- Ulangi langkah 2 sampai semua node telah "dikunjungi" atau tidak ada lagi node yang dapat dijangkau dari node sumber.

Pada setiap langkah, algoritma selalu memilih node yang terdekat yang belum dikunjungi, memastikan bahwa setiap kali kita mengupdate jarak, kita selalu mempertimbangkan jalur yang paling efisien.

Contoh Permasalahan

Bayangkan Anda memiliki peta jalan dengan kota-kota sebagai node dan jalanan sebagai edge. Setiap jalan memiliki bobot (misalnya, jarak dalam kilometer). Anda ingin menemukan jalur terpendek dari Kota A ke Kota E.

Grafik Contoh:

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

Tujuan: Temukan jalur terpendek dari A ke E.

Langkah-langkah sederhana (ilustratif):

Inisialisasi: jarak(A)=0, jarak(B)=inf, dst. Node yang belum dikunjungi: (A, B, C, D, E, F)
Pilih A (jarak 0):
- Tetangga B: jarak(A) + 1 = 1. jarak(B) diupdate jadi 1.
- Tetangga D: jarak(A) + 5 = 5. jarak(D) diupdate jadi 5.
Pilih B (jarak 1):
- Tetangga A: Sudah dikunjungi.
- Tetangga C: jarak(B) + 4 = 5. jarak(C) diupdate jadi 5.
- Tetangga E: jarak(B) + 2 = 3. jarak(E) diupdate jadi 3.
Pilih E (jarak 3):
- Tetangga B: Sudah dikunjungi.
- Tetangga D: jarak(E) + 3 = 6. (A-B-E-D). Bandingkan dengan jarak(D) saat ini (5). 5 lebih kecil, jadi jarak(D) tidak diupdate.
- Tetangga F: jarak(E) + 1 = 4. jarak(F) diupdate jadi 4.

Proses ini terus berlanjut hingga semua node terjangkau memiliki jalur terpendek yang ditemukan. Jalur terpendek dari A ke E adalah A -> B -> E dengan total jarak 3.

Implementasi Kode (C++)

Berikut adalah contoh implementasi Algoritma Dijkstra sederhana menggunakan C++. Dalam proyek Next.js 14, Anda mungkin akan berinteraksi dengan algoritma ini melalui API atau library yang ditulis dalam bahasa lain (misalnya Python atau JavaScript untuk backend), atau mengimplementasikannya dalam JavaScript/TypeScript jika grafiknya kecil dan di sisi klien.

#include <iostream>
#include <vector>
#include <queue>
#include <limits> // For numeric_limits

const int INF = std::numeric_limits<int>::max(); // Representasi tak terbatas

// Struktur untuk menyimpan node dan bobotnya
struct Edge {
    int to;
    int weight;
};

// Fungsi perbandingan untuk priority queue (min-heap)
// Akan mengurutkan berdasarkan jarak terkecil
struct CompareDistance {
    bool operator()(const std::pair<int, int>& a, const std::pair<int, int>& b) {
        return a.second > b.second; // Urutkan berdasarkan jarak (nilai kedua) secara ascending
    }
};

void dijkstra(const std::vector<std::vector<Edge>>& graph, int startNode, int numNodes) {
    std::vector<int> dist(numNodes, INF); // Jarak dari startNode ke setiap node
    std::vector<int> prev(numNodes, -1); // Untuk merekonstruksi jalur
    dist[startNode] = 0;

    // Priority queue: pair<jarak, node>
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, CompareDistance> pq;
    pq.push({startNode, 0}); // Masukkan node awal dengan jarak 0

    while (!pq.empty()) {
        int u = pq.top().first;
        int d = pq.top().second;
        pq.pop();

        // Jika jarak yang ditemukan lebih besar dari yang sudah ada, lewati
        if (d > dist[u]) {
            continue;
        }

        // Iterasi melalui tetangga dari node u
        for (const Edge& edge : graph[u]) {
            int v = edge.to;
            int weight = edge.weight;

            // Jika ditemukan jalur yang lebih pendek ke node v
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                prev[v] = u; // Simpan node sebelumnya untuk rekonstruksi jalur
                pq.push({v, dist[v]});
            }
        }
    }

    // Menampilkan hasil
    std::cout << "Jarak terpendek dari node " << startNode << ":\n";
    for (int i = 0; i < numNodes; ++i) {
        if (dist[i] == INF) {
            std::cout << "Node " << i << ": Tidak dapat dijangkau\n";
        } else {
            std::cout << "Node " << i << ": " << dist[i];
            // Tambahan: rekonstruksi jalur
            std::cout << " (Jalur: ";
            std::vector<int> path;
            int curr = i;
            while (curr != -1) {
                path.insert(path.begin(), curr);
                curr = prev[curr];
            }
            for (size_t j = 0; j < path.size(); ++j) {
                std::cout << path[j];
                if (j < path.size() - 1) {
                    std::cout << " -> ";
                }
            }
            std::cout << ")\n";
        }
    }
}

int main() {
    int numNodes = 6; // Contoh: 6 node (0 hingga 5)
    std::vector<std::vector<Edge>> graph(numNodes);

    // Menambahkan edge (sesuai contoh grafik di atas)
    graph[0].push_back({1, 1}); // A to B
    graph[0].push_back({3, 5}); // A to D
    graph[1].push_back({0, 1}); // B to A (untuk grafik tak berarah, tambahkan keduanya)
    graph[1].push_back({2, 4}); // B to C
    graph[1].push_back({4, 2}); // B to E
    graph[2].push_back({1, 4}); // C to B
    graph[2].push_back({5, 1}); // C to F
    graph[3].push_back({0, 5}); // D to A
    graph[3].push_back({4, 3}); // D to E
    graph[4].push_back({1, 2}); // E to B
    graph[4].push_back({3, 3}); // E to D
    graph[4].push_back({5, 1}); // E to F
    graph[5].push_back({2, 1}); // F to C
    graph[5].push_back({4, 1}); // F to E

    dijkstra(graph, 0, numNodes); // Jalankan Dijkstra dari node 0 (A)

    return 0;
}

Kelebihan dan Kekurangan

Kelebihan Algoritma Dijkstra:

Menemukan Jalur Terpendek Optimal: Dijamin akan menemukan jalur terpendek dari satu sumber ke semua node lain dalam grafik dengan bobot sisi non-negatif.
Relatif Mudah Dipahami: Konsep dasarnya cukup intuitif, mengikuti pendekatan "greedy" (selalu memilih jalur terpendek saat ini).
Banyak Digunakan: Fondasi bagi banyak aplikasi dunia nyata.

Kekurangan Algoritma Dijkstra:

Tidak Bisa Menangani Bobot Sisi Negatif: Jika ada sisi dengan bobot negatif, algoritma ini tidak akan bekerja dengan benar dan bisa menghasilkan jalur yang salah. Untuk kasus ini, algoritma seperti Bellman-Ford lebih cocok.
Kompleksitas Waktu: Untuk grafik yang sangat padat atau sangat besar, kompleksitas waktu (O(E log V) atau O(V^2) tergantung implementasi) bisa menjadi masalah kinerja.

Kesimpulan

Algoritma Dijkstra adalah alat yang sangat kuat dan efisien untuk menemukan jalur terpendek dalam grafik berbobot dengan bobot sisi positif. Pemahamannya adalah langkah kunci dalam mempelajari algoritma grafik dan memiliki aplikasi praktis yang luas di berbagai bidang. Meskipun memiliki batasan (tidak menangani bobot negatif), keandalannya dalam skenario yang tepat menjadikannya salah satu algoritma yang harus Anda kuasai.