Penerapan Djikstra dalam pencarian jarak terdekat

 Full Code : 

#include <iostream>

#include <vector>

#include <queue>

#include <climits>

#include <algorithm>

using namespace std;

struct Edge {

    int targetNode;

    int weight;

};

void printPath(int target, const vector<int>& parent) {

    vector<int> path;

    for (int curr = target; curr != -1; curr = parent[curr]) {

        path.push_back(curr);

    }

    reverse(path.begin(), path.end());

    for (size_t i = 0; i < path.size(); ++i) {

        cout << path[i];

        if (i < path.size() - 1) {

            cout << " -> ";

        }

    }

}

void dijkstra(int source, int destination, int totalNodes, const vector<vector<Edge>>& graph) {

    vector<int> distance(totalNodes, INT_MAX);

   

    vector<int> parent(totalNodes, -1);

   

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    distance[source] = 0;

    pq.push({0, source});

    while (!pq.empty()) {

        int currentNode = pq.top().second;

        int currentDistance = pq.top().first;

        pq.pop();

        if (currentNode == destination) break;

        if (currentDistance > distance[currentNode]) continue;

        for (const Edge& edge : graph[currentNode]) {

            int neighbor = edge.targetNode;

            int weight = edge.weight;

            if (distance[currentNode] + weight < distance[neighbor]) {

                distance[neighbor] = distance[currentNode] + weight;

                parent[neighbor] = currentNode; // Catat dari mana asal jalur ini

                pq.push({distance[neighbor], neighbor});

            }

        }

    }

    cout << "\n=============================================\n";

    cout << "               HASIL PENCARIAN RUTE          \n";

    cout << "=============================================\n";

   

    if (distance[destination] == INT_MAX) {

        cout << "Tidak ada jalur yang menghubungkan Node [" << source << "] ke Node [" << destination << "].\n";

    } else {

        cout << "Jalur/Rute Terbaik : ";

        printPath(destination, parent);

        cout << "\nTotal Waktu Tempuh : " << distance[destination] << " satuan waktu\n";

    }

    cout << "=============================================\n";

}

int main() {

    int nodes, edges;

   

    cout << "==================================================\n";

    cout << "  PROGRAM DIJKSTRA: HITUNG RUTE & WAKTU TEMPUH\n";

    cout << "==================================================\n";

   

    cout << "Masukkan jumlah total Node/Vertiks: ";

    cin >> nodes;

    cout << "Masukkan jumlah total Edge/Sisi: ";

    cin >> edges;

    vector<vector<Edge>> graph(nodes);

    cout << "\nSilahkan masukkan data Edge dengan format: [Node_Asal] [Node_Tujuan] [Waktu/Bobot]\n";

    cout << "Catatan: Penomoran node dimulai dari 0 sampai " << nodes - 1 << "\n";

    cout << "-------------------------------------------------------------------------\n";

   

    for (int i = 0; i < edges; ++i) {

        int u, v, w;

        cout << "Edge ke-" << i + 1 << ": ";

        cin >> u >> v >> w;

       

        if (u < 0 || u >= nodes || v < 0 || v >= nodes) {

            cout << "Input salah! Node harus berada di antara 0 sampai " << nodes - 1 << ".\n";

            i--;

            continue;

        }

       

        graph[u].push_back({v, w});

    }

    int source, destination;

    cout << "\nMasukkan Node Awal: ";

    cin >> source;

    cout << "Masukkan Node Tujuan: ";

    cin >> destination;

    if (source >= 0 && source < nodes && destination >= 0 && destination < nodes) {

        dijkstra(source, destination, nodes, graph);

    } else {

        cout << "Error: Node awal atau tujuan tidak valid (di luar batas)!\n";

    }

    return 0;

}

1. Analisis Fungsi Satu per Satu

void printPath(int target, const vector<int>& parent)

• Kegunaan: Fungsi ini bertanggung jawab untuk merekonstruksi dan mencetak jalur rute yang dilewati dari titik asal (source) hingga ke titik tujuan (target).

• Cara Kerja: Algoritma Dijkstra mencatat rute secara terbalik (dari belakang ke depan) menggunakan vektor parent. Fungsi ini melakukan perulangan mundur (curr = parent[curr]) mulai dari node tujuan hingga menemukan -1 (tanda bahwa kita sudah sampai di node asal). Karena urutannya terbalik, fungsi menggunakan reverse() agar rute dicetak dengan benar (misal: 1 -> 3 -> 2 -> 4).

void dijkstra(int source, int destination, int totalNodes, const vector<vector<Edge>>& graph)

• Kegunaan: Ini adalah inti/jantung dari seluruh program. Fungsi ini menghitung rute terpendek/tercepat menggunakan Algoritma Dijkstra dari satu titik asal ke satu titik tujuan spesifik.

• Komponen di Dalamnya:

  • vector<int> distance: Menyimpan catatan akumulasi waktu/jarak terpendek sementara dari node asal ke node lainnya. Diinisialisasi dengan nilai tak hingga (INT_MAX).

  • vector<int> parent: Peta ingatan untuk mencatat "sebelum ke node X, kita paling cepat lewat node mana?". Ini digunakan oleh fungsi printPath.

  • priority_queue<...> (Min-Heap): Antrean prioritas yang otomatis menempatkan node dengan bobot akumulasi terkecil di posisi paling atas (pq.top()), sehingga program selalu mengeksplorasi jalur paling menjanjikan terlebih dahulu.

• Optimasi Penting: Ada baris if (currentNode == destination) break;. Artinya, jika antrean prioritas sudah mengangkat node tujuan kita, algoritma akan langsung berhenti saat itu juga tanpa perlu memeriksa sisa node lain yang tidak penting.

int main()

• Kegunaan: Menjadi pintu masuk utama program sekaligus pengatur antarmuka interaktif dengan pengguna.

• Tugas Utamanya:

  1. Meminta input jumlah total node dan edge dari pengguna.

  2. Membangun struktur graf dalam bentuk Adjacency List (vector<vector<Edge>> graph).

  3. Mengamankan program dari crash melalui validasi batas indeks (if (u < 0 || u >= nodes ...)). Jika kamu memasukkan nomor node yang tidak terdaftar, program tidak akan eror, melainkan memintamu mengulang input.

  4. Menerima input titik awal dan akhir, lalu memanggil fungsi dijkstra().

2. Kegunaan dan Filosofi Algoritma Dijkstra

Algoritma Dijkstra adalah algoritma Greedy yang dirancang untuk mencari lintasan terpendek (single-source shortest path) dari satu titik acuan ke titik-titik lain pada graf yang memiliki bobot edge bernilai positif >=0.

Dalam konteks kode yang kamu tulis, kegunaan praktisnya meliputi:

• Navigasi Gps / Maps: Menemukan rute perjalanan dari titik A ke titik B dengan akumulasi lampu merah atau kemacetan (bobot/waktu) paling minimal.

• Routing Jaringan Komputer: Mengirimkan paket data dari komputer pengirim ke komputer penerima melalui jalur router yang memiliki latensi (ping) paling kecil agar transfer data super cepat.

• Logistik dan Distribusi: Membantu kurir atau armada pengiriman barang memilih kombinasi jalan raya yang menghemat waktu tempuh dan bahan bakar.

Mengapa algoritma ini sangat efisien?

Dibandingkan mencoba semua kemungkinan rute satu per satu (Brute Force) yang memakan waktu lama, Dijkstra menerapkan prinsip Relaksasi.

Setiap kali ia menemukan jalur baru menuju suatu node yang ternyata menghasilkan total waktu lebih kecil daripada catatan waktu lama, ia langsung memperbarui data di dalam tabel distance dan parent-nya. Berkat bantuan priority_queue, algoritma ini bekerja dengan efisiensi waktu sebesar O((V + E) \log V), di mana V adalah jumlah Node dan E adalah jumlah Edge.