Algoritma Dijkstra

Tugas Pertemuan ke-15  ·  Struktur Data - D

Implementasi Algoritma Dijkstra
dalam C++

Mencari rute pengiriman tercepat pada studi kasus Food Delivery menggunakan Graph berbobot dan Algoritma Dijkstra dengan optimasi Priority Queue (Min Heap).

GitHub Repository

Mata KuliahStruktur Data - D

Pertemuanke-15

BahasaC++

Topik UtamaAlgoritma Dijkstra

Apa Itu Algoritma Dijkstra?

Algoritma Dijkstra adalah algoritma pencarian jalur terpendek (shortest path) dari satu simpul sumber ke simpul tujuan pada graph berbobot positif. Algoritma ini menjadi tulang punggung sistem navigasi nyata seperti Google Maps, ride-hailing, dan logistik karena selalu menjamin jalur dengan total bobot minimum.

Studi Kasus: Food Delivery

Layanan pengantaran makanan harus menentukan jalur tercepat dari Restoran menuju Pelanggan. Rute yang tidak optimal berdampak langsung pada waktu pengiriman, biaya operasional, dan kepuasan pelanggan. Jaringan jalan dimodelkan sebagai graph: setiap lokasi adalah vertex, dan setiap jalan penghubung adalah edge dengan bobot berupa waktu tempuh (menit).

🗺️

Representasi Memodelkan jaringan jalan sebagai Graph berbobot

⚙️

Implementasi Menerapkan Dijkstra dalam bahasa C++

🚀

Optimasi Menentukan rute tercepat Restoran → Pelanggan

⏱️

Hasil Menghitung total waktu tempuh minimum

Data & Representasi Graph

Data Lokasi (Vertex)

R = Restoran
A = Perempatan A
B = Perempatan B
C = Perempatan C
D = Perempatan D
E = Perempatan E
P = Pelanggan

Data Waktu Tempuh (Edge, menit)

R→A = 4    A→B = 3    C→D = 4
R→B = 2    A→E = 6    D→P = 3
R→C = 7    B→C = 3    E→P = 4
           B→D = 2
           B→E = 3

Visualisasi Graph Berbobot

Jalur hijau = rute tercepat R → B → D → P (7 menit)

Cara Kerja Algoritma

1

Tetapkan node awal (sumber); beri jarak 0 pada sumber dan ∞ pada node lain.

2

Pilih node dengan jarak terkecil yang belum diproses (lewat Priority Queue).

3

Perbarui (relax) jarak seluruh tetangga jika ditemukan jalur lebih pendek.

4

Ulangi sampai semua node selesai; rekonstruksi jalur lewat array parent.

---

Implementasi Program C++

dijkstra_food_delivery.cpp C++

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 1000000000;

int main() {
    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});  // graph tak berarah
    };

    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), parent(n, -1);

    // Min-Heap: ambil node jarak terkecil secara efisien
    priority_queue<pair<int,int>,
        vector<pair<int,int>>,
        greater<pair<int,int>>> pq;

    int start = 0, 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;  // entri usang, lewati

        for (auto edge : graph[u]) {
            int v = edge.first, w = edge.second;
            if (dist[u] + w < dist[v]) {   // proses relaksasi
                dist[v]   = dist[u] + w;
                parent[v] = u;
                pq.push({dist[v], v});
            }
        }
    }

    // Rekonstruksi jalur dari goal ke start
    vector<int> path;
    for (int v = goal; v != -1; v = parent[v])
        path.push_back(v);
    reverse(path.begin(), path.end());

    cout << "===== FOOD DELIVERY =====\n\n";
    cout << "Rute Tercepat : \n";
    for (int i = 0; i < path.size(); i++) {
        cout << lokasi[path[i]];
        if (i < path.size()-1) cout << " -> ";
    }
    cout << "\n\nTotal Waktu Tempuh : " << dist[goal] << " menit\n";
    return 0;
}

Output Program

Terminal Output

===== FOOD DELIVERY =====

Rute Tercepat :
Restoran -> B -> D -> Pelanggan

Total Waktu Tempuh : 7 menit

⚠️ Catatan Teknis Pengecekan if (d > dist[u]) continue; wajib ada. Karena node bisa masuk priority_queue lebih dari sekali, baris ini membuang entri jarak yang sudah usang sehingga algoritma tetap efisien dan tidak memproses ulang node yang jaraknya sudah final.

---

Pelacakan Langkah (Step Trace)

Berikut perubahan nilai dist[] setiap kali sebuah node diambil dari Priority Queue dan diproses. Nilai hijau menandakan jarak yang sudah final (node selesai diproses).

Proses Node	R	A	B	C	D	E	P
Inisialisasi	0	∞	∞	∞	∞	∞	∞
R (0)	0	4	2	7	∞	∞	∞
B (2)	0	4	2	5	4	5	∞
A (4)	0	4	2	5	4	5	∞
D (4)	0	4	2	5	4	5	7
C (5)	0	4	2	5	4	5	7
E (5)	0	4	2	5	4	5	7
P (7)	0	4	2	5	4	5	7

Terlihat saat node D diproses, jarak ke P diperbarui menjadi 7 (4 + 3). Jalur via E juga mencapai P dengan nilai 9, namun karena 7 < 9 maka parent[P] tetap menunjuk ke D — menghasilkan rute final R → B → D → P.

---

Analisis Hasil

Algoritma menemukan jalur tercepat dengan total waktu tempuh 7 menit. Dibandingkan jalur alternatif lain, rute via Perempatan B dan D jelas paling optimal:

R → B → D → P 7 menit Optimal

R → B → E → P 9 menit

R → A → E → P 14 menit

R → C → D → P 14 menit

Kompleksitas Algoritma

O((V + E) log V)

Menggunakan Priority Queue (Min Heap), pencarian node berjarak minimum jauh lebih efisien dibanding pencarian linear O(V²). Pada studi kasus ini V = 7 vertex dan E = 11 edge.

Kelebihan & Kekurangan

✅ Kelebihan

• Menjamin jalur terpendek optimal pada graph berbobot positif
• Efisien untuk sistem navigasi, GPS, dan logistik
• Mudah dikombinasikan dengan Priority Queue
• Sekali jalan menghasilkan jarak terpendek ke semua node

⚠️ Kekurangan

• Tidak bisa menangani edge berbobot negatif (gunakan Bellman-Ford)
• Kompleksitas naik pada graph yang sangat besar
• Butuh memori tambahan untuk array dist & parent

Kesimpulan

Algoritma Dijkstra terbukti efektif menentukan jalur tercepat pada graph berbobot positif. Pada studi kasus Food Delivery, graph memodelkan jaringan jalan dan bobot edge mewakili waktu tempuh.

Restoran → B → D → Pelanggan  =  7 menit

Dengan optimasi Priority Queue, Dijkstra menjadi fondasi solusi navigasi dan optimasi rute. Konsep ini bisa dikembangkan ke algoritma graph lain:

Bellman-Ford A* Search Floyd-Warshall BFS / DFS Minimum Spanning Tree