Struktur Data - Penerapan Algoritma Djikstra

Nama    : Aga Nafta Filadelfiano

NRP      : 5025251055
Kelas     : Struktur Data (D) 

Penerapan Algoritma Djikstra

Source Code: GitHub

Studi Kasus Food Delivery Menggunakan Bahasa C++

Deskripsi: 

Layanan Food Delivery membutuhkan sistem yang mampu menentukan rute tercepat dari restoran

menuju pelanggan. Pemilihan rute yang tidak optimal dapat menyebabkan keterlambatan pengiriman,

meningkatnya biaya operasional, dan menurunnya kepuasan pelanggan. Untuk mengatasi permasalahan tersebut digunakan Algoritma Dijkstra yang mampu mencari jalur terpendek pada graph berbobot positif.

Tujuan:

- Merepresentasikan jaringan jalan dalam bentuk graph berbobot.

- Mengimplementasikan Algoritma Dijkstra menggunakan C++.

- Menentukan jalur tercepat dari Restoran ke Pelanggan.

- Menampilkan total waktu tempuh minimum.

Data Lokasi:

               

Data Bobot Waktu Tempuh:

    


Representasi Graph:

Algoritma yang Digunakan:

- Menetapkan node awal.

- Memberikan jarak 0 pada node awal dan tak hingga pada node lainnya.

- Memilih node dengan jarak terkecil.

- Memperbarui jarak tetangga.

- Mengulangi proses sampai seluruh node selesai diproses.

Syntax Program:

Output:

Penjelasan Code:

vector<string> lokasi = {"Restoran", "A", "B", "C", "D", "E", "Pelanggan"};

int n = 7;

vector<pair<int, int>> graph[7];

auto addEdge = [&](int u, int v, int w) {

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

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

};

addEdge(0, 1, 4); // Restoran ke A beban 4

addEdge(0, 2, 2); // Restoran ke B beban 2

• Daftar Tempat: lokasi menyimpan nama titik yang diwakili oleh angka indeks (0 = Restoran, 1 = A, dst, hingga 6 = Pelanggan).
• Membuat Peta (graph): graph[7] adalah tempat untuk menyimpan jalur antar tempat beserta bobotnya (waktu tempuh).
• Fungsi addEdge: Ini adalah fungsi pembantu pendek untuk menghubungkan dua lokasi. Karena jalan sifatnya dua arah, jika kita hubungkan lokasi u ke v, maka v juga otomatis terhubung kembali ke u.

vector<int> dist(n, INF);

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

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

int start = 0; // Mulai dari Restoran

dist[start] = 0;

pq.push({0, start});

• Pencatat Jarak (dist): Sebuah daftar untuk mencatat waktu tempuh ke semua lokasi. Awalnya diisi INF (angka yang sangat besar) karena kita belum tahu jarak aslinya.
• Pencatat Jejak (parent): Digunakan untuk mencatat "tadi dari lokasi mana sebelum sampai sini", agar nanti rutenya bisa dilacak ulang.
• Antrean Pintar (pq): Antrean khusus (Priority Queue) yang bertugas memilih lokasi mana yang punya waktu tempuh paling kecil/cepat untuk diproses duluan.
• Titik Mulai: Kita mulai dari start = 0 (Restoran), jadi jarak ke diri sendiri diatur 0, lalu dimasukkan ke dalam antrean.

while (!pq.empty()) {

    int u = pq.top().second; // Ambil lokasi saat ini

    pq.pop();

    for (auto edge : graph[u]) {

        int v = edge.first;  // Lokasi tetangga

        int w = edge.second; // Waktu tempuh ke tetangga

        if (dist[u] + w < dist[v]) {

            dist[v] = dist[u] + w;

            parent[v] = u; // Catat jalurnya

            pq.push({dist[v], v});

        }

    }

}

• Perulangan while: Program akan terus berjalan selama masih ada lokasi di dalam antrean untuk diperiksa.
• Cek Tetangga: Program melihat semua lokasi tetangga (v) yang terhubung dengan lokasi kita saat ini (u).
• Update Jarak Terbaik: Jika jalan lewat lokasi u ternyata lebih cepat daripada jarak yang dicatat sebelumnya (dist[u] + w < dist[v]), maka catatan jarak diperbarui dengan waktu yang lebih singkat tersebut.
• Simpan Jejak: Saat jarak diperbarui, program juga mencatat bahwa untuk ke lokasi v, jalur terbaiknya adalah lewat u (parent[v] = u).

vector<int> path;

for (int v = goal; v != -1; v = parent[v]) {

    path.push_back(v);

}

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

cout << "Total Waktu Tempuh : " << dist[goal] << " menit\n";

• Melacak Mundur: Karena kita tahu titik akhirnya (Pelanggan), kode melacak mundur menggunakan catatan parent sampai kembali ke titik awal (Restoran).
• Membalik Rute (reverse): Hasil pelacakan mundur tadi kan terbalik (Pelanggan -> ... -> Restoran). Fungsi reverse digunakan untuk membaliknya lagi agar urutannya benar dari Restoran ke Pelanggan.
• Cetak Hasil: Terakhir, program mencetak nama-nama lokasi yang dilewati dan total menit tercepat yang tersimpan di dist[goal].

Analisis Hasil:

Algoritma Dijkstra berhasil menemukan rute tercepat dari Restoran menuju Pelanggan.

Perhitungan:

Restoran → B = 2 menit

B → D = 2 menit

D → Pelanggan = 3 menit

Total:

2 + 2 + 3 = 7 menit

Perbandingan dengan rute lain:

R → A → E → P = 14 menit

R → C → D → P = 14 menit

R → B → E → P = 9 menit

Maka jalur melalui B dan D merupakan jalur optimal.

Kompleksitas Algoritma:

Dengan Priority Queue:

O((V + E) log V)

Keterangan:

V = jumlah vertex

E = jumlah edge

Pada kasus ini:

V = 7

E = 11

Kesimpulan:

Algoritma Dijkstra dapat digunakan untuk menentukan rute tercepat pada sistem Food Delivery. Graph berbobot digunakan untuk merepresentasikan jaringan jalan dan waktu tempuh. Implementasi menggunakan Priority Queue menghasilkan proses pencarian yang efisien. 

Jalur tercepat yang diperoleh adalah:

Restoran → B → D → Pelanggan

dengan total waktu tempuh 7 menit.