Pertemuan 15 - Studi Kasus Algoritma Dijkstra

 

Algoritma Dijkstra di C++

Nama: Hadryan Rizky Dimas Saputra

NRP: 5025251027

Kelas: Struktur Data (D) 2026

Pertemuan: 15

Source Code: pertemuan_15

Studi Kasus: Food Delivery dengan Algoritma Dijkstra di C++

Deskripsi (Fungsi) Program: 

Algoritma Dijkstra digunakan dan mampu mencari jalur terpendek pada graph berbobot positif. Algoritma Dijkstra bekerja dengan langkah: 

1. Menetapkan node awal. 

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

3. Memilih node dengan jarak terkecil. 

4. Memperbarui jarak tetangga. 

5. Mengulangi proses sampai seluruh node selesai diproses.  

Code:

/*

Implementasi Algoritma Dijkstra dalam C++

Studi Kasus: Food Delivery

*/

#include <bits/stdc++.h>

using namespace std;

const int INF = 1000000000;

int main(void) {

vector<string> loc = {

"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);

addEdge(0, 2, 2);

addEdge(0, 3, 7);

addEdge(1, 2, 3);

addEdge(1, 5, 6);

addEdge(2, 3, 3);

addEdge(2, 4, 2);

addEdge(2, 5, 3);

addEdge(3, 4, 4);

addEdge(4, 6, 3);

addEdge(5, 6, 4);

vector<int> dist(n, INF);

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

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

int start = 0;

int goal = 6;

dist[start] = 0;

pq.push({0, start});

while(!pq.empty()) {

int d = pq.top().first;

int u = pq.top().second;

pq.pop();

if(d > dist[u]) {

continue;

}

for(auto edge : graph[u]) {

int v = edge.first;

int w = edge.second;

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

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

par[v] = u;

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

}

}

}

vector<int> path;

int i;

for(i = goal; i != -1; i = par[i]) {

path.push_back(i);

}

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

cout << "=== FOOD DELIVERY ===\n\n";

cout << "Rute Tercepat: \n";

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

cout << loc[path[i]];

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

cout << " -> ";

}

}

cout << "\n\n";

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

return 0;

}

Hasil/Output Program:

Penjelasan Program:

Baris Kode	Penjelasan
/* ... */	Komentar judul studi kasus program
#include <bits/stdc++.h>	Memasukkan pustaka/library standar C++
using namespace std;	Menggunakan standar pustaka C++ (namespace std)
const int INF = 1000000000;	Mendeklarasikan konstanta INF untuk representasi nilai tak terhingga
int main(void) {	Memulai program fungsi utama tempat eksekusi berjalan
vector<string> loc = { ... };	Mendeklarasikan nama node/lokasi string dalam bentuk vector array
int n = 7;	Menyimpan total jumlah node (7 lokasi)
vector<pair<int, int>> graph[7];	Membuat adjacency list pada graf untuk menampung node tujuan dan bobotnya
auto addEdge = [&](int u, int v, int w) { ... };	Fungsi lambda untuk menambahkan data jalan dan waktu tempuh (bobot) antarnode
graph[u].push_back({v, w});	Menambahkan titik v dengan bobot w ke daftar tetangga pada node asal u
graph[v].push_back({u, w});	Menambahkan titik u dengan bobot w ke daftar tetangga pada node asal v (untuk graf tak berarah)
addEdge(...);	Menambahkan rute dan data bobot antar lokasi satu per satu ke dalam graf
vector<int> dist(n, INF);	Menyimpan rekam jarak terpendek dan menginisialisasi semua jarak dengan INF
vector<int> par(n, -1);	Menyimpan daftar riwayat asal rute (parent) dan menginisialisasi dengan -1
priority_queue<...>	Membuat priority queue (min-heap) untuk terus mengevaluasi rute dengan jarak terpendek
int start = 0;	Mendefinisikan ID node indeks 0 (Restoran) sebagai awal rute keberangkatan
int goal = 6;	Mendefinisikan ID node indeks 6 (Pelanggan) sebagai titik tujuan akhir rute
dist[start] = 0;	Menyetel nilai jarak ke node awal (dirinya sendiri) menjadi 0
pq.push({0, start});	Memasukkan titik awal ke dalam antrean (pq) untuk diproses terlebih dahulu
while(!pq.empty()) {	Memulai perulangan pencarian selama priority queue belum kosong
int d = pq.top().first;	Mengambil jarak akumulasi terpendek yang ada di puncak antrean
int u = pq.top().second;	Mengambil indeks identitas node dengan jarak terpendek tersebut
pq.pop();	Menghapus node teratas di antrean setelah diproses
if(d > dist[u]) continue;	Mengabaikan langkah jika akumulasi jarak saat ini lebih besar daripada jarak minimum yang telah tercatat
for(auto edge : graph[u]) {	Memulai iterasi untuk melihat setiap rute tetangga dari node u
int v = edge.first;	Mengambil identitas indeks node tujuan tetangga
int w = edge.second;	Mengambil bobot waktu tempuh dari node u menuju v
if(dist[u] + w < dist[v]) {	Memeriksa apakah melalui titik saat ini akan mendapatkan waktu total lebih singkat
dist[v] = dist[u] + w;	Memperbarui rute tercepat ke node tujuan v jika ditemukan rute yang lebih singkat
par[v] = u;	Menyimpan sejarah pergerakan dengan mengingat u adalah parent dari v
pq.push({dist[v], v});	Memasukkan pembaruan rute ke dalam priority queue
vector<int> path;	Menyiapkan array (vector) untuk menampung hasil urutan jalan akhir
int i;	Inisialisasi variabel untuk keperluan iterasi pelacakan hasil (backtracking)
for(i = goal; i != -1; i = par[i]) {	Mengurutkan rekam jejak mulai titik tujuan hingga titik awal keberangkatan
path.push_back(i);	Menyimpan pelacakan parent titik tersebut ke dalam susunan rute path
reverse(path.begin(), path.end());	Membalikkan array path agar rute berurutan dari keberangkatan menuju kedatangan
cout << "=== FOOD DELIVERY ===\n\n";	Mencetak header teks antarmuka awal ke layar
cout << "Rute Tercepat: \n";	Mencetak tulisan rute tercepat ke layar
for(i = 0; i < path.size(); i++) {	Memulai perulangan untuk mencetak nama lokasi dari array path
cout << loc[path[i]];	Mencetak nama titik jalan riilnya sesuai pencocokan indeks dengan array string loc
if(i < path.size() - 1) { cout << " -> "; }	Mencetak format garis arah/panah untuk tampilan grafis jalan antarnode
cout << "\n\n";	Mencetak garis baru vertikal di ujung output
cout << "Total Waktu Ditempuh: " ...	Mencetak total hasil pengkalkulasian waktu tercepat akhir dari dist[goal]
return 0;	Fungsi main sukses dieksekusi sampai tuntas