Chapter Graph memperkenalkan BFS dan DFS pada graf tak berbobot: berapa pun panjangnya, satu busur dihitung satu langkah. Peta jalan nyata tidak seadil itu — satu busur bisa berarti 200 meter dan yang lain 40 kilometer. Chapter ini menambahkan bobot pada setiap busur dan menjalankan Dijkstra, algoritma jarak terpendek dari satu sumber, di atas adjacency list dan std::priority_queue. Kita juga kembali ke DFS untuk satu tugas penting yang belum dikerjakan: mendeteksi siklus pada graf berarah, kemampuan dasar di balik pemeriksaan dependensi dan topological sort. Seperti pada chapter Graph, seluruh hasil dirancang deterministik: urutan output selalu sama di setiap eksekusi.

Dijkstra: Jarak Terpendek dari Satu Sumber #

Dijkstra adalah greedy yang bisa dibuktikan benar — pola dari chapter Greedy Algorithms kembali bekerja. Strateginya: selalu proses simpul yang belum final dengan jarak sementara terkecil, tandai jaraknya final, lalu perbarui tetangganya. Min-heap dari priority_queue mengantre simpul berdasarkan jarak sementara, sehingga pilihan “terkecil berikutnya” hanya memerlukan satu pop:

cpp 
// Dijkstra (adjacency list + priority_queue) dan deteksi siklus dengan DFS.
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

using Busur = std::pair<int, int>;  // (simpul tujuan, bobot)

// Dijkstra: jarak terpendek dari satu sumber, bobot tak negatif.
// priority_queue min-heap menyimpan (jarak, simpul); entri basi dilewati.
void dijkstra(const std::vector<std::vector<Busur>>& tetangga, int sumber,
              std::vector<int>& jarak, std::vector<int>& pendahulu) {
    int n = static_cast<int>(tetangga.size());
    jarak.assign(n, 1000000);        // "tak hingga" versi praktis
    pendahulu.assign(n, -1);
    std::vector<bool> final(n, false);
    jarak[sumber] = 0;
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
                        std::greater<std::pair<int, int>>>
        antre;  // pasangan (jarak, simpul); greater = min-heap
    antre.push({0, sumber});
    while (!antre.empty()) {
        auto [d, u] = antre.top();
        antre.pop();
        if (final[u]) continue;      // entri basi: simpul sudah diproses
        final[u] = true;
        for (auto [v, bobot] : tetangga[u]) {
            if (!final[v] && d + bobot < jarak[v]) {
                jarak[v] = d + bobot;
                pendahulu[v] = u;
                antre.push({jarak[v], v});
            }
        }
    }
}

// Rekonstruksi jalur sumber -> tujuan dari array pendahulu.
std::vector<int> jalurKe(const std::vector<int>& pendahulu, int tujuan) {
    std::vector<int> jalur;
    for (int v = tujuan; v != -1; v = pendahulu[v]) jalur.push_back(v);
    return std::vector<int>(jalur.rbegin(), jalur.rend());
}

// Deteksi siklus graf BERARAH: DFS tiga warna.
// 0 = putih (belum dikunjungi), 1 = abu (di tumpukan rekursi), 2 = hitam.
bool adaSiklus(int u, const std::vector<std::vector<int>>& tetangga,
               std::vector<int>& warna) {
    warna[u] = 1;  // masuk: tandai abu
    for (int v : tetangga[u]) {
        if (warna[v] == 1) return true;  // menemui abu: kembali ke leluhur
        if (warna[v] == 0 && adaSiklus(v, tetangga, warna)) return true;
    }
    warna[u] = 2;  // selesai: tandai hitam
    return false;
}

void cetakJalur(const std::vector<int>& jalur) {
    for (std::size_t i = 0; i < jalur.size(); ++i) {
        if (i > 0) std::cout << " -> ";
        std::cout << jalur[i];
    }
}

int main() {
    // Graf berarah berbobot: 6 simpul, simpul 5 sengaja tak tersambung.
    std::vector<std::vector<Busur>> g(6);
    auto tambah = [&g](int u, int v, int w) { g[u].push_back({v, w}); };
    tambah(0, 1, 4);
    tambah(0, 2, 1);
    tambah(2, 1, 2);
    tambah(1, 3, 5);
    tambah(2, 3, 8);
    tambah(3, 4, 2);
    tambah(2, 4, 7);

    std::vector<int> jarak, pendahulu;
    dijkstra(g, 0, jarak, pendahulu);
    std::cout << "Jarak terpendek dari simpul 0:\n";
    for (int v = 0; v < static_cast<int>(g.size()); ++v) {
        if (jarak[v] >= 1000000) {
            std::cout << "  simpul " << v << ": tak terjangkau\n";
        } else {
            std::cout << "  simpul " << v << ": " << jarak[v]
                      << "  jalur: ";
            cetakJalur(jalurKe(pendahulu, v));
            std::cout << '\n';
        }
    }

    // Deteksi siklus pada dua graf berarah.
    std::vector<std::vector<int>> dag(4);
    dag[0] = {1, 2};
    dag[1] = {2};
    dag[2] = {3};
    std::vector<int> warnaA(4, 0);
    std::cout << "Graf A (DAG) : "
              << (adaSiklus(0, dag, warnaA) ? "ada siklus"
                                            : "tidak ada siklus") << '\n';

    std::vector<std::vector<int>> berputar(4);
    berputar[0] = {1};
    berputar[1] = {2};
    berputar[2] = {0, 3};
    std::vector<int> warnaB(4, 0);
    std::cout << "Graf B       : "
              << (adaSiklus(0, berputar, warnaB) ? "ada siklus"
                                                 : "tidak ada siklus") << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
Jarak terpendek dari simpul 0:
  simpul 0: 0  jalur: 0
  simpul 1: 3  jalur: 0 -> 2 -> 1
  simpul 2: 1  jalur: 0 -> 2
  simpul 3: 8  jalur: 0 -> 2 -> 1 -> 3
  simpul 4: 8  jalur: 0 -> 2 -> 4
  simpul 5: tak terjangkau
Graf A (DAG) : tidak ada siklus
Graf B       : ada siklus

Bedah baris penting:

  1. Baris 11-41 (dijkstra): array jarak diinisialisasi “tak hingga” (1000000 versi praktis), lalu sumber diset 0 dan masuk antrean.
  2. Baris 17-19: greater<> mengubah priority_queue menjadi min-heap — pasangan (jarak, simpul) terkecil muncul paling dulu.
  3. Baris 25-26: pemeriksaan final[u] melewatkan entri basi. Satu simpul bisa terdorong ke antrean berkali-kali dengan jarak yang makin baik; hanya dorongan terbaik yang diproses, sisanya dibuang begitu keluar.
  4. Baris 27-32: relaksasi — jika lewat u lebih cepat, perbarui jarak[v], catat pendahulu[v] = u, dan dorong simpul v yang baru.
  5. Baris 38-41 (jalurKe): array pendahulu ditelusuri mundur dari tujuan lalu dibalik menjadi jalur utuh.
  6. Baris 64-75: graf uji memuat trik yang segera terlihat di output: busur langsung 0 -> 1 berbobot 4, tetapi rute 0 -> 2 -> 1 hanya 3.

Merekonstruksi Jalur dengan Array Pendahulu #

Angka saja sering tidak cukup — navigasi perlu menunjukkan rutenya. Setiap kali relaksasi memperbarui jarak[v], program mencatat pendahulu[v] = u: siapa yang membawa kita ke v. Setelah algoritma selesai, jalur ke simpul mana pun tersusun dengan mundur dari tujuan sampai sumber, lalu dibalik. Itulah yang dicetak di kolom jalur pada output.

Baris simpul 1 memperlihatkan nilai utama bobot: jalur terpilih adalah 0 -> 2 -> 1 dengan total 3, mengalahkan busur langsung 0 -> 1 yang berbobot 4. Tanpa bobot, BFS akan menganggap kedua opsi sama panjang. Baris terakhir tabel juga mengajarkan penanganan kasus yang sering lupa: simpul 5 tidak memiliki satu pun busur, sehingga jaraknya tetap “tak hingga” dan program mencetak tak terjangkau alih-alih angka yang menyesatkan.

Deteksi Siklus dengan DFS Tiga Warna #

DFS pada chapter Graph memakai satu penanda boolean: dikunjungi atau belum. Untuk graf berarah, satu boolean tidak cukup menjawab pertanyaan “apakah ada siklus”, karena bertemunya dua simpul yang sudah dikunjungi belum tentu artinya kembali ke titik awal. Solusinya tiga warna:

  • Putih: simpul belum dikunjungi sama sekali.
  • Abu: sedang berada di tumpukan rekursi — jalur menyelam saat ini masih melewatinya.
  • Hitam: penjelajahan dari simpul itu sudah selesai dan aman.
cpp 
// Potongan dari graph-algorithms.cpp (fungsi adaSiklus, baris 48-57)
bool adaSiklus(int u, const std::vector<std::vector<int>>& tetangga,
               std::vector<int>& warna) {
    warna[u] = 1;  // masuk: tandai abu
    for (int v : tetangga[u]) {
        if (warna[v] == 1) return true;  // menemui abu: kembali ke leluhur
        if (warna[v] == 0 && adaSiklus(v, tetangga, warna)) return true;
    }
    warna[u] = 2;  // selesai: tandai hitam
    return false;
}

Aturannya satu kalimat: bertemu simpul abu berarti kita kembali ke leluhur di tumpukan rekursi — itulah siklus. Bertemu hitam tidak berbahaya, karena hitam sudah selesai diperiksa tanpa menemukan jalan kembali. Output program menunjukkan kedua kasus: Graf A (DAG, directed acyclic graph) lolos tanpa siklus, sedangkan Graf B yang memuat busur 2 -> 0 tertangkap. Pemeriksaan ini adalah setengah dari topological sort — mengurutkan simpul DAG agar setiap dependensi terpenuhi dulu — yang kini sudah dalam jangkauan Anda.

Dijkstra cepat bukan kebetulan: ia berdiri di atas kombinasi yang tepat — adjacency list untuk menghindari memori V², min-heap untuk memilih kandidat terbaik, dan array pendahulu untuk menyimpan jalur. Kombinasi yang tepat adalah tema yang akan kita rangkum langsung: chapter berikutnya, penutup section ini, menyusun seluruh struktur data dan algoritma yang sudah kita kuasai menjadi satu tabel keputusan.

Rujukan resmi: std::priority_queue dan std::greater .