Bab Graph telah membekali kita dengan adjacency list dan adjacency matrix; sekarang saatnya meletakkan algoritma di atasnya. Banyak persoalan dunia nyata berbentuk jaringan — rute pengiriman, prasyarat mata kuliah, koneksi antar server — dan tiga pertanyaan muncul berulang kali: berapa lompatan minimum antara dua simpul, apakah jaringan memuat siklus, dan jalur termurah mana pada jaringan yang tiap sisinya punya bobot. BFS menjawab pertanyaan pertama, DFS menjawab yang kedua, dan Dijkstra dengan PriorityQueue menjawab yang ketiga. Bab ini menerapkan ketiganya pada graph kota Java dengan data tetap, lalu membandingkan kompleksitasnya dalam satu tabel.

BFS untuk Jarak Paling Sedikit Lompatan #

Breadth-First Search (BFS) menjelajahi graph berlapis-lapis: simpul awal, lalu semua tetangganya, lalu tetangga dari tetangganya. Sifat berlapis inilah yang membuat BFS cocok mencari jarak pada graph tak berbobot — simpul yang lebih dulu masuk antrean selalu memiliki jarak lompatan yang paling kecil. Program berikut menghitung jarak setiap kota dari Jakarta dan merekonstruksi jalurnya:

java BfsJalur.java 
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class BfsJalur {

    // Adjacency list kota tak berarah; satu sisi = satu lompatan.
    private final Map<String, List<String>> tetangga = new LinkedHashMap<>();

    public static void main(String[] args) {
        BfsJalur graph = new BfsJalur();
        graph.tambahSisi("Jakarta", "Bandung");
        graph.tambahSisi("Jakarta", "Semarang");
        graph.tambahSisi("Bandung", "Yogyakarta");
        graph.tambahSisi("Semarang", "Yogyakarta");
        graph.tambahSisi("Semarang", "Surabaya");
        graph.tambahSisi("Yogyakarta", "Surabaya");

        Map<String, Integer> jarakLompatan = graph.jarakLompatan("Jakarta");
        System.out.println("=== BFS dari Jakarta: jarak minimum dalam lompatan ===");
        for (Map.Entry<String, Integer> e : jarakLompatan.entrySet()) {
            System.out.printf("  %-10s %d lompatan%n", e.getKey(), e.getValue());
        }

        System.out.println();
        System.out.println("Jalur ke Surabaya : " + graph.jalurKe("Surabaya", jarakLompatan));
        System.out.println("Jalur ke Yogyakarta: " + graph.jalurKe("Yogyakarta", jarakLompatan));
    }

    void tambahSisi(String a, String b) {
        tetangga.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
        tetangga.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
    }

    // BFS: setiap kota diproses berdasarkan urutan masuk antrean,
    // sehingga jarak pertama yang tercatat selalu yang paling sedikit lompatan.
    Map<String, Integer> jarakLompatan(String mulai) {
        Map<String, Integer> jarak = new LinkedHashMap<>();
        Deque<String> antrean = new ArrayDeque<>();
        jarak.put(mulai, 0);
        antrean.add(mulai);
        while (!antrean.isEmpty()) {
            String kota = antrean.poll();
            for (String tetanggaKota : tetangga.get(kota)) {
                if (!jarak.containsKey(tetanggaKota)) {
                    jarak.put(tetanggaKota, jarak.get(kota) + 1);
                    antrean.add(tetanggaKota);
                }
            }
        }
        return jarak;
    }

    // Jalur direkonstruksi dengan berjalan mundur: cari tetangga
    // yang jaraknya tepat satu lebih kecil, lalu ulangi sampai titik awal.
    List<String> jalurKe(String tujuan, Map<String, Integer> jarak) {
        List<String> jalur = new ArrayList<>(List.of(tujuan));
        String kota = tujuan;
        while (jarak.get(kota) > 0) {
            for (String kandidat : tetangga.get(kota)) {
                if (jarak.get(kandidat) == jarak.get(kota) - 1) {
                    jalur.add(0, kandidat);
                    kota = kandidat;
                    break;
                }
            }
        }
        return jalur;
    }
}

Output yang Dihasilkan:

text 
=== BFS dari Jakarta: jarak minimum dalam lompatan ===
  Jakarta    0 lompatan
  Bandung    1 lompatan
  Semarang   1 lompatan
  Yogyakarta 2 lompatan
  Surabaya   2 lompatan

Jalur ke Surabaya : [Jakarta, Semarang, Surabaya]
Jalur ke Yogyakarta: [Jakarta, Bandung, Yogyakarta]

Hasilnya sesuai intuisi: Surabaya berjarak dua lompatan melalui Semarang, Yogyakarta juga dua lompatan melalui Bandung. Trik pentingnya ada pada gabungan Map dan antrean — peta jarak sekaligus berperan sebagai penanda visited, karena kunci yang sudah ada tidak akan ditimpa.

Bedah baris-per-baris untuk bagian intinya:

  1. Baris 43-45 (jarak.put(mulai, 0); antrean.add(mulai)): BFS dimulai dengan satu simpul berjarak nol. Konstruksi ini menjaga invarian penting: setiap elemen di antrean sudah punya jarak final.
  2. Baris 48 (String kota = antrean.poll()): antrean FIFO (first in first out) mengeluarkan simpul yang paling lama menunggu. Karena penyisipan dilakukan berlapis, urutan keluar mengikuti urutan jarak — inilah mekanisme yang membuat BFS menemukan jarak minimum tanpa perlu menimbang apa pun.
  3. Baris 50 (if (!jarak.containsKey(tetanggaKota))): kandidat yang sudah punya jarak dilewati. Jarak pertama yang tercatat tidak mungkin diperbaiki lagi pada graph tak berbobot, sehingga pemeriksaan ini sekaligus mencegah simpul masuk antrean dua kali.
  4. Baris 51-52 (jarak.put(...); antrean.add(...)): tetangga baru mendapat jarak = jarak simpul sekarang + 1, lalu mengantre. Setiap sisi dan simpun dikunjungi tepat satu kali, sehingga total kompleksitas O(V + E).

DFS dan Deteksi Siklus #

Depth-First Search (DFS) menempuh jalur yang berbeda: menelusuri sejauh mungkin ke satu arah sebelum mundur (backtrack). Karakter inilah yang dimanfaatkan untuk mendeteksi siklus pada directed graph — penelusuran yang menemukan simpul yang sedang diproses berarti ada jalur melingkar. Contoh nyatanya adalah prasyarat mata kuliah: bila Algoritma menuntut StrukturData dan StrukturData menuntut Algoritma, tidak ada urutan pengambilan yang sah. Program berikut memakai pewarnaan tiga status:

java DfsSiklus.java 
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class DfsSiklus {

    // Warna status DFS pada directed graph:
    // 1 = putih (belum dikunjungi), 2 = abu-abu (sedang diproses), 3 = hitam (selesai).
    private static final int PUTIH = 1, ABU = 2, HITAM = 3;

    private final Map<String, List<String>> sisi = new LinkedHashMap<>();
    private final Map<String, Integer> status = new LinkedHashMap<>();

    public static void main(String[] args) {
        DfsSiklus matakuliah = new DfsSiklus();
        matakuliah.prasyarat("DasarPemrograman", "OOP");
        matakuliah.prasyarat("DasarPemrograman", "StrukturData");
        matakuliah.prasyarat("StrukturData", "Algoritma");
        matakuliah.prasyarat("OOP", "BasisData");
        matakuliah.prasyarat("Algoritma", "KeamananAplikasi");

        System.out.println("=== Kartu rencana studi tanpa siklus ===");
        System.out.println("Siklus terdeteksi: " + matakuliah.adaSiklus());

        // Tambahkan prasyarat balik: Algoritma menuntut DasarPemrograman.
        matakuliah.prasyarat("Algoritma", "DasarPemrograman");

        System.out.println();
        System.out.println("=== Setelah menambah sisi Algoritma -> DasarPemrograman ===");
        System.out.println("Siklus terdeteksi: " + matakuliah.adaSiklus());
    }

    void prasyarat(String dari, String ke) {
        sisi.computeIfAbsent(dari, k -> new ArrayList<>()).add(ke);
        sisi.computeIfAbsent(ke, k -> new ArrayList<>());
    }

    boolean adaSiklus() {
        for (String node : sisi.keySet()) {
            status.put(node, PUTIH);
        }
        for (String node : sisi.keySet()) {
            if (status.get(node) == PUTIH && dfsDeteksi(node)) {
                return true;
            }
        }
        return false;
    }

    // DFS rekursif: node berstatus abu-abu berarti node itu berada
    // di jalur penelusuran saat ini, jadi sisi menuju node itu menutup siklus.
    private boolean dfsDeteksi(String node) {
        status.put(node, ABU);
        for (String tujuan : sisi.get(node)) {
            if (status.get(tujuan) == ABU) {
                System.out.println("  Sisi " + node + " -> " + tujuan
                        + " kembali ke node yang masih diproses");
                return true;
            }
            if (status.get(tujuan) == PUTIH && dfsDeteksi(tujuan)) {
                return true;
            }
        }
        status.put(node, HITAM);
        return false;
    }
}

Output yang Dihasilkan:

text 
=== Kartu rencana studi tanpa siklus ===
Siklus terdeteksi: false

=== Setelah menambah sisi Algoritma -> DasarPemrograman ===
  Sisi Algoritma -> DasarPemrograman kembali ke node yang masih diproses
Siklus terdeteksi: true

Skenario pertama menghasilkan false — kelima mata kuliah membentuk hierarki yang bersih. Skenario kedua baru menangkap siklus setelah sisi balik Algoritma → DasarPemrograman ditambahkan, dan program melaporkan sisi mana yang menutup lingkaran itu.

Mari kita bedah pewarnaan statusnya:

  1. Baris 61 (status.put(node, ABU)): simpul dicat abu-abu saat penelusuran masuk ke simpul itu. Selama masih abu-abu, simpul berada di call stack rekursi — artinya simpul adalah bagian dari jalur yang sedang diperiksa.
  2. Baris 64-68 (if (status.get(tujuan) == ABU)): sisi yang menuju simpul abu-abu membentuk jalur melingkar, karena simpul tujuan adalah leluhur dari simpul asal pada pohon rekursi. Pemeriksaan inilah deteksi siklus sesungguhnya.
  3. Baris 74 (status.put(node, HITAM)): simpul dicat hitam setelah semua keturunannya selesai ditelusuri. Sisi menuju simpul hitam aman dilewati — jalur itu sudah pernah dijelajahi menyeluruh dan terbukti tidak mengandung siklus yang melewati simpul sekarang.

Dijkstra pada Graph Berbobot #

Ketika setiap sisi membawa bobot — kilometer, tarif, waktu — BFS tidak lagi memadai karena dua lompatan bisa lebih mahal daripada lima lompatan. Algoritma Dijkstra menyelesaikannya dengan PriorityQueue: simpul dengan total jarak sementara terkecil selalu diproses lebih dulu, dan setiap relaksasi sisi dapat memperbarui jarak sementara tetangganya. Program berikut mencari rute termurah dari Jakarta ke seluruh kota pada peta sembilan jalan:

java DijkstraKota.java 
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public class DijkstraKota {

    // Sisi berbobot: kota tujuan dan jarak tempuh dalam kilometer.
    record Sisi(String tujuan, int jarak) { }

    // Entri antrean prioritas: kota dan jarak sementara terbaik yang diketahui.
    record Entri(String kota, int jarakSementara) { }

    private final Map<String, List<Sisi>> jalan = new LinkedHashMap<>();
    private final Map<String, String> induk = new HashMap<>(); // untuk rekonstruksi rute

    public static void main(String[] args) {
        DijkstraKota peta = new DijkstraKota();
        peta.tambahJalan("Jakarta", "Bandung", 150);
        peta.tambahJalan("Jakarta", "Semarang", 450);
        peta.tambahJalan("Jakarta", "Surabaya", 810);
        peta.tambahJalan("Bandung", "Yogyakarta", 430);
        peta.tambahJalan("Semarang", "Yogyakarta", 125);
        peta.tambahJalan("Semarang", "Surabaya", 350);
        peta.tambahJalan("Yogyakarta", "Surabaya", 260);
        peta.tambahJalan("Surabaya", "Denpasar", 500);
        peta.tambahJalan("Yogyakarta", "Denpasar", 900);

        Map<String, Integer> jarak = peta.jarakTerpendek("Jakarta");
        System.out.println("=== Dijkstra dari Jakarta (jarak dalam km) ===");
        for (Map.Entry<String, Integer> e : jarak.entrySet()) {
            System.out.printf("  %-10s %d km%n", e.getKey(), e.getValue());
        }

        System.out.println();
        System.out.println("Rute ke Denpasar : " + peta.ruteKe("Denpasar"));
        System.out.println("Rute ke Yogyakarta: " + peta.ruteKe("Yogyakarta"));
    }

    void tambahJalan(String dari, String ke, int jarak) {
        jalan.computeIfAbsent(dari, k -> new ArrayList<>()).add(new Sisi(ke, jarak));
        jalan.computeIfAbsent(ke, k -> new ArrayList<>());
    }

    Map<String, Integer> jarakTerpendek(String mulai) {
        Map<String, Integer> jarak = new LinkedHashMap<>();
        Map<String, String> induk = new HashMap<>();
        for (String kota : jalan.keySet()) {
            jarak.put(kota, Integer.MAX_VALUE);
        }
        jarak.put(mulai, 0);

        PriorityQueue<Entri> antrean = new PriorityQueue<>(
                Comparator.comparingInt(Entri::jarakSementara));
        antrean.add(new Entri(mulai, 0));

        while (!antrean.isEmpty()) {
            Entri sekarang = antrean.poll();
            if (sekarang.jarakSementara() > jarak.get(sekarang.kota())) {
                continue; // Entri basi: kota ini sudah ditemukan lewat rute lebih pendek.
            }
            for (Sisi sisi : jalan.get(sekarang.kota())) {
                int kandidat = sekarang.jarakSementara() + sisi.jarak();
                if (kandidat < jarak.get(sisi.tujuan())) {
                    jarak.put(sisi.tujuan(), kandidat);
                    induk.put(sisi.tujuan(), sekarang.kota());
                    antrean.add(new Entri(sisi.tujuan(), kandidat));
                }
            }
        }
        return jarak;
    }

    String ruteKe(String tujuan) {
        List<String> rute = new ArrayList<>(List.of(tujuan));
        String kota = tujuan;
        while (induk.containsKey(kota)) {
            kota = induk.get(kota);
            rute.add(0, kota);
        }
        return String.join(" -> ", rute);
    }
}

Output yang Dihasilkan:

text 
=== Dijkstra dari Jakarta (jarak dalam km) ===
  Jakarta    0 km
  Bandung    150 km
  Semarang   450 km
  Surabaya   800 km
  Yogyakarta 575 km
  Denpasar   1300 km

Rute ke Denpasar : Denpasar
Rute ke Yogyakarta: Yogyakarta

Output memperlihatkan jebakan jalan langsung: sisi Jakarta → Surabaya sepanjang 810 km kalah oleh rute memutar Jakarta → Semarang → Surabaya yang totalnya hanya 800 km. Denpasar pun ternyata paling murah dicapai lewat Surabaya (total 1300 km), bukan lewat jalan langsung dari Yogyakarta yang berharga 900 km dari Yogyakarta ditambah 575 km perjalanan ke sana.

Bedah baris-per-baris untuk mesin Dijkstra-nya:

  1. Baris 58-62 (inisialisasi Integer.MAX_VALUE): semua kota dianggap tak terjangkau kecuali titik awal berjarak nol. Nilai sentinel Integer.MAX_VALUE membuat relaksasi pertama selalu berhasil.
  2. Baris 65-66 (PriorityQueue dengan Comparator.comparingInt): record Entri dibandingkan berdasarkan jarak sementaranya, sehingga poll() selalu mengembalikan kota termurah yang belum final. Bandingkan dengan BFS yang memakai antrean FIFO — perbedaan kecil ini yang mengubah kemampuan algoritma.
  3. Baris 70-72 (lewatkan entri basi): satu kota bisa masuk antrean berkali-kali setiap kali jarak sementaranya membaik. Entri lama dikenali dari jarakSementara yang lebih besar daripada nilai terkini di peta jarak, lalu dilewati. Pendekatan lazy deletion ini lebih sederhana daripada memindahkan elemen di dalam heap.
  4. Baris 74-79 (relaksasi sisi): untuk setiap tetangga, kandidat = jarak simpul sekarang + bobot sisi. Bila kandidat lebih murah dari catatan lama, peta jarak diperbarui, peta induk merekam asal rute, dan entri baru masuk antrean.
  5. Baris 84-91 (ruteKe): rute dibangun mundur dari tujuan ke titik awal mengikuti peta induk, lalu dibalik dengan menyisipkan di posisi nol. Teknik rekonstruksi ini sama persis dengan yang dipakai BFS — hanya sumber jejaknya berbeda.

Perbandingan Kompleksitas #

Ketiga algoritma memindai graph dengan cara berbeda, dan biayanya pun berbeda:

AlgoritmaStruktur intiKompleksitas waktuMenjawab
BFSAntrean FIFOO(V + E)Jarak lompatan minimum pada graph tak berbobot
DFSCall stack (rekursi atau stack eksplisit)O(V + E)Siklus, urutan topologis, komponen terhubung
DijkstraPriorityQueue (binary heap)O((V + E) log V)Jarak termurah pada graph berbobot non-negatif

Ketiga algoritma ini menutup daftar teknik klasik pada Section. Seluruh bekal sudah di tangan: kompleksitas, struktur data, rekursi, greedy, DP, dan kini graph. Bab terakhir mengubah kumpulan teknik itu menjadi praktik rekayasa — dari spesifikasi berisi kalimat, menjadi class, method, dan pengujian yang rapi dalam bahasa Java.

Referensi #

Berkas Sumber

Berkas pendukung halaman ini dapat diunduh dan dijalankan langsung sesuai penjelasan di atas.

BfsJalur.java

Unduh berkas
java 
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class BfsJalur {

    // Adjacency list kota tak berarah; satu sisi = satu lompatan.
    private final Map<String, List<String>> tetangga = new LinkedHashMap<>();

    public static void main(String[] args) {
        BfsJalur graph = new BfsJalur();
        graph.tambahSisi("Jakarta", "Bandung");
        graph.tambahSisi("Jakarta", "Semarang");
        graph.tambahSisi("Bandung", "Yogyakarta");
        graph.tambahSisi("Semarang", "Yogyakarta");
        graph.tambahSisi("Semarang", "Surabaya");
        graph.tambahSisi("Yogyakarta", "Surabaya");

        Map<String, Integer> jarakLompatan = graph.jarakLompatan("Jakarta");
        System.out.println("=== BFS dari Jakarta: jarak minimum dalam lompatan ===");
        for (Map.Entry<String, Integer> e : jarakLompatan.entrySet()) {
            System.out.printf("  %-10s %d lompatan%n", e.getKey(), e.getValue());
        }

        System.out.println();
        System.out.println("Jalur ke Surabaya : " + graph.jalurKe("Surabaya", jarakLompatan));
        System.out.println("Jalur ke Yogyakarta: " + graph.jalurKe("Yogyakarta", jarakLompatan));
    }

    void tambahSisi(String a, String b) {
        tetangga.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
        tetangga.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
    }

    // BFS: setiap kota diproses berdasarkan urutan masuk antrean,
    // sehingga jarak pertama yang tercatat selalu yang paling sedikit lompatan.
    Map<String, Integer> jarakLompatan(String mulai) {
        Map<String, Integer> jarak = new LinkedHashMap<>();
        Deque<String> antrean = new ArrayDeque<>();
        jarak.put(mulai, 0);
        antrean.add(mulai);
        while (!antrean.isEmpty()) {
            String kota = antrean.poll();
            for (String tetanggaKota : tetangga.get(kota)) {
                if (!jarak.containsKey(tetanggaKota)) {
                    jarak.put(tetanggaKota, jarak.get(kota) + 1);
                    antrean.add(tetanggaKota);
                }
            }
        }
        return jarak;
    }

    // Jalur direkonstruksi dengan berjalan mundur: cari tetangga
    // yang jaraknya tepat satu lebih kecil, lalu ulangi sampai titik awal.
    List<String> jalurKe(String tujuan, Map<String, Integer> jarak) {
        List<String> jalur = new ArrayList<>(List.of(tujuan));
        String kota = tujuan;
        while (jarak.get(kota) > 0) {
            for (String kandidat : tetangga.get(kota)) {
                if (jarak.get(kandidat) == jarak.get(kota) - 1) {
                    jalur.add(0, kandidat);
                    kota = kandidat;
                    break;
                }
            }
        }
        return jalur;
    }
}

DfsSiklus.java

Unduh berkas
java 
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class DfsSiklus {

    // Warna status DFS pada directed graph:
    // 1 = putih (belum dikunjungi), 2 = abu-abu (sedang diproses), 3 = hitam (selesai).
    private static final int PUTIH = 1, ABU = 2, HITAM = 3;

    private final Map<String, List<String>> sisi = new LinkedHashMap<>();
    private final Map<String, Integer> status = new LinkedHashMap<>();

    public static void main(String[] args) {
        DfsSiklus matakuliah = new DfsSiklus();
        matakuliah.prasyarat("DasarPemrograman", "OOP");
        matakuliah.prasyarat("DasarPemrograman", "StrukturData");
        matakuliah.prasyarat("StrukturData", "Algoritma");
        matakuliah.prasyarat("OOP", "BasisData");
        matakuliah.prasyarat("Algoritma", "KeamananAplikasi");

        System.out.println("=== Kartu rencana studi tanpa siklus ===");
        System.out.println("Siklus terdeteksi: " + matakuliah.adaSiklus());

        // Tambahkan prasyarat balik: Algoritma menuntut DasarPemrograman.
        matakuliah.prasyarat("Algoritma", "DasarPemrograman");

        System.out.println();
        System.out.println("=== Setelah menambah sisi Algoritma -> DasarPemrograman ===");
        System.out.println("Siklus terdeteksi: " + matakuliah.adaSiklus());
    }

    void prasyarat(String dari, String ke) {
        sisi.computeIfAbsent(dari, k -> new ArrayList<>()).add(ke);
        sisi.computeIfAbsent(ke, k -> new ArrayList<>());
    }

    boolean adaSiklus() {
        for (String node : sisi.keySet()) {
            status.put(node, PUTIH);
        }
        for (String node : sisi.keySet()) {
            if (status.get(node) == PUTIH && dfsDeteksi(node)) {
                return true;
            }
        }
        return false;
    }

    // DFS rekursif: node berstatus abu-abu berarti node itu berada
    // di jalur penelusuran saat ini, jadi sisi menuju node itu menutup siklus.
    private boolean dfsDeteksi(String node) {
        status.put(node, ABU);
        for (String tujuan : sisi.get(node)) {
            if (status.get(tujuan) == ABU) {
                System.out.println("  Sisi " + node + " -> " + tujuan
                        + " kembali ke node yang masih diproses");
                return true;
            }
            if (status.get(tujuan) == PUTIH && dfsDeteksi(tujuan)) {
                return true;
            }
        }
        status.put(node, HITAM);
        return false;
    }
}

DijkstraKota.java

Unduh berkas
java 
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public class DijkstraKota {

    // Sisi berbobot: kota tujuan dan jarak tempuh dalam kilometer.
    record Sisi(String tujuan, int jarak) { }

    // Entri antrean prioritas: kota dan jarak sementara terbaik yang diketahui.
    record Entri(String kota, int jarakSementara) { }

    private final Map<String, List<Sisi>> jalan = new LinkedHashMap<>();
    private final Map<String, String> induk = new HashMap<>(); // untuk rekonstruksi rute

    public static void main(String[] args) {
        DijkstraKota peta = new DijkstraKota();
        peta.tambahJalan("Jakarta", "Bandung", 150);
        peta.tambahJalan("Jakarta", "Semarang", 450);
        peta.tambahJalan("Jakarta", "Surabaya", 810);
        peta.tambahJalan("Bandung", "Yogyakarta", 430);
        peta.tambahJalan("Semarang", "Yogyakarta", 125);
        peta.tambahJalan("Semarang", "Surabaya", 350);
        peta.tambahJalan("Yogyakarta", "Surabaya", 260);
        peta.tambahJalan("Surabaya", "Denpasar", 500);
        peta.tambahJalan("Yogyakarta", "Denpasar", 900);

        Map<String, Integer> jarak = peta.jarakTerpendek("Jakarta");
        System.out.println("=== Dijkstra dari Jakarta (jarak dalam km) ===");
        for (Map.Entry<String, Integer> e : jarak.entrySet()) {
            System.out.printf("  %-10s %d km%n", e.getKey(), e.getValue());
        }

        System.out.println();
        System.out.println("Rute ke Denpasar : " + peta.ruteKe("Denpasar"));
        System.out.println("Rute ke Yogyakarta: " + peta.ruteKe("Yogyakarta"));
    }

    void tambahJalan(String dari, String ke, int jarak) {
        jalan.computeIfAbsent(dari, k -> new ArrayList<>()).add(new Sisi(ke, jarak));
        jalan.computeIfAbsent(ke, k -> new ArrayList<>());
    }

    Map<String, Integer> jarakTerpendek(String mulai) {
        Map<String, Integer> jarak = new LinkedHashMap<>();
        Map<String, String> induk = new HashMap<>();
        for (String kota : jalan.keySet()) {
            jarak.put(kota, Integer.MAX_VALUE);
        }
        jarak.put(mulai, 0);

        PriorityQueue<Entri> antrean = new PriorityQueue<>(
                Comparator.comparingInt(Entri::jarakSementara));
        antrean.add(new Entri(mulai, 0));

        while (!antrean.isEmpty()) {
            Entri sekarang = antrean.poll();
            if (sekarang.jarakSementara() > jarak.get(sekarang.kota())) {
                continue; // Entri basi: kota ini sudah ditemukan lewat rute lebih pendek.
            }
            for (Sisi sisi : jalan.get(sekarang.kota())) {
                int kandidat = sekarang.jarakSementara() + sisi.jarak();
                if (kandidat < jarak.get(sisi.tujuan())) {
                    jarak.put(sisi.tujuan(), kandidat);
                    induk.put(sisi.tujuan(), sekarang.kota());
                    antrean.add(new Entri(sisi.tujuan(), kandidat));
                }
            }
        }
        return jarak;
    }

    String ruteKe(String tujuan) {
        List<String> rute = new ArrayList<>(List.of(tujuan));
        String kota = tujuan;
        while (induk.containsKey(kota)) {
            kota = induk.get(kota);
            rute.add(0, kota);
        }
        return String.join(" -> ", rute);
    }
}