Algoritma Dijkstra di C++ untuk Shortest Path

Dec 26, 2024

—

Algoritma Dijkstra adalah algoritma greedy yang digunakan untuk menemukan jalur terpendek dari simpul sumber ke semua simpul lain dalam graph berbobot positif. Algoritma ini sering digunakan untuk masalah jaringan seperti rute terpendek atau perhitungan biaya minimum.

Langkah-Langkah Algoritma Dijkstra

Inisialisasi jarak ke semua simpul sebagai tak terhingga (∞), kecuali simpul sumber yang diatur menjadi 0.
Gunakan struktur data seperti priority queue (min-heap) untuk menyimpan simpul berdasarkan jarak minimum.
Untuk setiap simpul:
- Ambil simpul dengan jarak minimum dari priority queue.
- Perbarui jarak ke tetangganya jika jalur baru lebih pendek.
Ulangi hingga semua simpul telah diproses atau queue kosong.

Kompleksitas:

Waktu: O((V+E)logV), dengan V sebagai jumlah simpul dan E sebagai jumlah sisi.
Ruang: O(V+E).

Implementasi Dijkstra di C++

Berikut adalah implementasi menggunakan Adjacency List dan Priority Queue dari library STL.

#include <iostream>
#include <vector>
#include <queue>
#include <climits> // Untuk INT_MAX
using namespace std;

// Pasangan (simpul, bobot)
typedef pair<int, int> pii;

// Fungsi untuk menambahkan edge ke graph
void addEdge(vector<vector<pii>>& graph, int u, int v, int weight) {
    graph[u].emplace_back(v, weight);
    graph[v].emplace_back(u, weight); // Jika graph tidak berarah
}

// Algoritma Dijkstra
vector<int> dijkstra(const vector<vector<pii>>& graph, int src) {
    int V = graph.size();
    vector<int> dist(V, INT_MAX); // Inisialisasi jarak
    priority_queue<pii, vector<pii>, greater<pii>> pq; // Min-Heap

    // Inisialisasi sumber
    dist[src] = 0;
    pq.emplace(0, src);

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

        // Jika jarak sekarang lebih besar dari jarak di array, abaikan
        if (currDist > dist[u]) continue;

        // Periksa semua tetangga
        for (auto& neighbor : graph[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;

            // Perbarui jarak jika lebih kecil
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.emplace(dist[v], v);
            }
        }
    }

    return dist;
}

int main() {
    int V = 6; // Jumlah simpul
    vector<vector<pii>> graph(V);

    // Tambahkan edge (simpul1, simpul2, bobot)
    addEdge(graph, 0, 1, 4);
    addEdge(graph, 0, 2, 4);
    addEdge(graph, 1, 2, 2);
    addEdge(graph, 1, 3, 5);
    addEdge(graph, 2, 3, 8);
    addEdge(graph, 2, 4, 10);
    addEdge(graph, 3, 4, 2);
    addEdge(graph, 3, 5, 6);
    addEdge(graph, 4, 5, 3);

    int source = 0;
    vector<int> distances = dijkstra(graph, source);

    // Cetak jarak terpendek dari sumber ke semua simpul
    cout << "Jarak terpendek dari simpul " << source << ":\n";
    for (int i = 0; i < distances.size(); i++) {
        cout << "Ke simpul " << i << ": ";
        if (distances[i] == INT_MAX) {
            cout << "Tidak terjangkau" << endl;
        } else {
            cout << distances[i] << endl;
        }
    }

    return 0;
}

Penjelasan Kode

Representasi Graph:
- Menggunakan adjacency list, di mana setiap simpul memiliki daftar tetangganya beserta bobotnya.
Priority Queue:
- Menyimpan pasangan (jarak, simpul) untuk memastikan simpul dengan jarak minimum selalu diambil lebih dulu.
- Menggunakan greater<pii> untuk membuat min-heap.
Inisialisasi:
- Jarak ke semua simpul diatur ke INT_MAX, kecuali simpul sumber yang diatur ke 0.
Proses Tetangga:
- Jika jarak melalui simpul saat ini lebih kecil, perbarui jarak dan tambahkan tetangga ke priority queue.

Contoh Input dan Output

Graph dengan 6 simpul:

   (0)--4--(1)--2--(2)
    |       |       |
    4       5       8
    |       |       |
   (2)----10--(4)--3--(5)
              |       |
              2       6

Output:

Jarak terpendek dari simpul 0:
Ke simpul 0: 0
Ke simpul 1: 4
Ke simpul 2: 4
Ke simpul 3: 9
Ke simpul 4: 11
Ke simpul 5: 14

Keuntungan Dijkstra

Efisien untuk graph berbobot positif.
Sangat cocok untuk jaringan transportasi dan telekomunikasi.

Jika Anda ingin penjelasan tambahan atau implementasi variasi lainnya seperti Bellman-Ford, beri tahu saya! 😊