Lintasan terpendek berbobot

Bobot mengubah soal lintasan terpendek secara mendasar, karena langkah yang sedikit tidak lagi berarti jarak yang pendek. Topik ini membangun algoritma Dijkstra di atas heap, menjelaskan mengapa bobot negatif merusak jaminannya, lalu memperkenalkan Bellman-Ford yang tetap benar pada graf berbobot negatif sekaligus mendeteksi siklus negatifnya. Ketiga demo berjalan pada graf kecil yang tetap, lengkap dengan rekonstruksi lintasan dan padanan Java untuk Dijkstra.

Ketika BFS tidak lagi cukup#

Pada graf berbobot, jarak diukur dari penjumlahan bobot tepi, sehingga lintasan dengan tepi paling sedikit bukan lagi lintasan yang termurah. BFS yang menghitung jarak per level tidak dapat memperbaiki keputusannya, karena simpul yang masuk antrian duluan belum tentu punya jarak kumulatif terkecil. Algoritma keluarga ini bekerja dengan satu operasi dasar bernama relaksasi (relaxation), yaitu memperbarui jarak simpul v menjadi jarak simpul u ditambah bobot tepi u-v bila nilainya lebih kecil dari yang tercatat. Seluruh perbedaan antar algoritma lintasan terpendek pada dasarnya berupa strategi memilih kapan relaksasi dilakukan.

Dua algoritma yang dibahas berbagi kerangka data yang sama, yaitu array jarak yang diisi tak hingga di awal dan nol pada sumbernya. Array induk mencatat asal setiap pembaruan sehingga lintasan dapat direkonstruksi seperti pada BFS. Yang membedakan keduanya adalah urutan simpul yang direlaksasi berikutnya.

Dijkstra dengan heap#

Dijkstra selalu memproses simpul yang jaraknya terkecil di antara kandidat yang belum selesai, dan heap minimum (min-heap) menjamin pemilihan itu berbiaya $O(\log V)$. Simpul yang keluar pertama kali dari heap sudah mencapai jarak finalnya, selama tidak ada bobot negatif. Setiap relaksasi yang berhasil mendorong pasangan (jarak, simpul) baru ke heap, sedangkan entri lama dibiarkan di dalamnya dan dibuang saat keluar. Dengan jumlah pendorongan yang sebanding $E$ dan tiap operasi heap berbiaya $O(\log V)$, total waktunya $O(E \log V)$.

Syarat bobot tak negatif bukan detail teknis, melainkan fondasi argumennya. Bila ada tepi negatif, simpul yang sudah dikeluarkan dari heap bisa ditemukan kembali dengan jarak lebih kecil lewat tepi negatif tersebut, dan keputusan finalnya terbukti salah. Bellman-Ford menggantikan argumen ini dengan perulangan relaksasi yang polos, dan keduanya dibandingkan di bagian akhir topik.

Diagram berikut memetakan graf berbobot contoh dengan sumber di simpul 0. Lintasan termurah menuju simpul 1 ternyata tidak langsung, melainkan berkelok lewat simpul 2 karena bobot 4 pada tepi 0-1 kalah dari gabungan 2 + 1. Jarak akhir seluruh simpul tercetak di dasar diagram dan cocok dengan keluaran demo.

Implementasi Dijkstra dengan heapq#

Berkas berikut membangun adjacency list berbobot, lalu menjalankan Dijkstra dengan heap yang isinya tupel (jarak, simpul). Urutan tupel penting, karena pembanding heap membaca elemen pertamanya sehingga entri berjarak terkecil selalu keluar duluan. Pengecekan entri usang di awal perulangan adalah bentuk lazy deletion yang paling sering dipakai.

# Dijkstra dengan heap: jarak terpendek dari simpul 0 pada graf berbobot.
import heapq

# Tepi (u, v, bobot) untuk graf tak berarah dengan enam simpul.
tepi = [(0, 1, 4), (0, 2, 2), (1, 2, 1), (1, 3, 5), (2, 3, 8),
        (3, 4, 2), (3, 5, 6), (4, 5, 3)]
n = 6

tetangga = [[] for _ in range(n)]
for u, v, w in tepi:
    tetangga[u].append((v, w))
    tetangga[v].append((u, w))

jarak = [float("inf")] * n
induk = [-1] * n
jarak[0] = 0
heap = [(0, 0)]  # setiap entri berupa tupel (jarak, simpul)
while heap:
    jarak_kini, simpul = heapq.heappop(heap)
    if jarak_kini > jarak[simpul]:
        continue  # entri usang: simpul sudah dicapai dengan jarak lebih kecil
    for t, bobot in tetangga[simpul]:
        jarak_baru = jarak_kini + bobot
        if jarak_baru < jarak[t]:
            jarak[t] = jarak_baru
            induk[t] = simpul
            heapq.heappush(heap, (jarak_baru, t))

print("Jarak dari 0   :", jarak)

# Rekonstruksi lintasan 0 -> 5 dengan menyusuri rantai induk.
lintasan = []
simpul = 5
while simpul != -1:
    lintasan.append(simpul)
    simpul = induk[simpul]
lintasan.reverse()
print("Lintasan 0 -> 5:", lintasan)

Jarak dari 0   : [0, 3, 2, 8, 10, 13]
Lintasan 0 -> 5: [0, 2, 1, 3, 4, 5]

Jarak [0, 3, 2, 8, 10, 13] menegaskan lintasan menuju 1 yang berkelok lewat 2, dan lintasan menuju 5 direkonstruksi dari rantai induk menjadi 0, 2, 1, 3, 4, 5 dengan total bobot 13. Perhatikan tepi 2 menuju 3 berbobot 8 yang tidak pernah dipakai, karena jalan lewat 1 lebih murah. Menyimpan induk saat relaksasi berhasil membuat rekonstruksi lintasan tetap gratis seperti pada BFS.

Padanan Java dengan PriorityQueue#

Kelas PriorityQueue berperan sebagai heap, dan pembandingnya ditulis sebagai selisih jarak pada pasangan larik {jarak, simpul}. Struktur dan pengecekan entri usangnya sama persis dengan versi Python, sehingga yang perlu diperhatikan hanya pola deklarasinya. Larik jarak diisi Integer.MAX_VALUE sebagai tak hingga karena Java tidak punya literal tak hingga untuk bilangan bulat.

// Dijkstra dengan PriorityQueue: jarak terpendek pada graf berbobot.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class DijkstraGraf {
    public static void main(String[] args) {
        int n = 6;
        int[][] tepi = {
            {0, 1, 4}, {0, 2, 2}, {1, 2, 1}, {1, 3, 5},
            {2, 3, 8}, {3, 4, 2}, {3, 5, 6}, {4, 5, 3}
        };

        List<List<int[]>> tetangga = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            tetangga.add(new ArrayList<>());
        }
        for (int[] e : tepi) {
            tetangga.get(e[0]).add(new int[]{e[1], e[2]});
            tetangga.get(e[1]).add(new int[]{e[0], e[2]});
        }

        int[] jarak = new int[n];
        Arrays.fill(jarak, Integer.MAX_VALUE);
        // entri heap berupa larik {jarak, simpul}, diurutkan menurut jarak
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        jarak[0] = 0;
        heap.add(new int[]{0, 0});
        while (!heap.isEmpty()) {
            int[] atas = heap.poll();
            int jarakKini = atas[0];
            int simpul = atas[1];
            if (jarakKini > jarak[simpul]) {
                continue; // entri usang, lewati
            }
            for (int[] t : tetangga.get(simpul)) {
                int jarakBaru = jarakKini + t[1];
                if (jarakBaru < jarak[t[0]]) {
                    jarak[t[0]] = jarakBaru;
                    heap.add(new int[]{jarakBaru, t[0]});
                }
            }
        }
        System.out.println("Jarak dari 0: " + Arrays.toString(jarak));
    }
}

Jarak dari 0: [0, 3, 2, 8, 10, 13]

Keluaran jaraknya identik dengan versi Python, yaitu [0, 3, 2, 8, 10, 13]. Satu catatan kecil, pembanding a[0] - b[0] aman selama jaraknya tidak mendekati batas bilangan bulat, dan bila bobotnya besar, ganti dengan Integer.compare. Untuk ukuran soal wawancara, bentuk ini sudah menjadi templat yang lazim.

Bellman-Ford untuk bobot negatif#

Bellman-Ford melepas asumsi Dijkstra dengan cara yang paling sederhana, yaitu merelaksasi seluruh tepi berulang-ulang tanpa memilih simpul terbaik. Setelah V - 1 putaran penuh, jarak setiap simpul sudah final. Alasannya, lintasan terpendek tanpa siklus paling banyak memuat V - 1 tepi, dan setiap putaran memastikan setidaknya satu tepi lagi tersambung pada lintasannya. Total biayanya $O(V \cdot E)$, lebih lambat dari Dijkstra tetapi tetap benar pada bobot negatif. Putaran pada berkas demo dihentikan lebih awal bila satu putaran penuh tidak menghasilkan pembaruan.

Deteksi siklus negatif memanfaatkan putaran tambahan, yaitu bila setelah V - 1 putaran masih ada tepi yang bisa merelaksasi, pasti ada siklus dengan total bobot negatif yang terus memperpendek lintasan. Demo menjalankan dua kasus, graf dengan satu tepi negatif yang sehat, lalu graf yang sama ditambah tepi (5, 3, -1) yang menutup siklus 3 menuju 4 menuju 5 menuju 3 dengan total -2. Kasus kedua membuat jarak-jaraknya terus merosot ke nilai yang tak berarti, dan detektornya menangkapnya sebagai True.

# Bellman-Ford: relaksasi V-1 kali, aman untuk bobot negatif.

def bellman_ford(daftar_tepi, n, sumber=0):
    jarak = [float("inf")] * n
    jarak[sumber] = 0
    for _ in range(n - 1):
        selesai = True
        for u, v, w in daftar_tepi:
            if jarak[u] != float("inf") and jarak[u] + w < jarak[v]:
                jarak[v] = jarak[u] + w
                selesai = False
        if selesai:
            break  # tidak ada pembaruan berarti jarak sudah final
    return jarak

def ada_siklus_negatif(daftar_tepi, n, jarak):
    for u, v, w in daftar_tepi:
        if jarak[u] != float("inf") and jarak[u] + w < jarak[v]:
            return True  # masih bisa diperpendek setelah V-1 putaran
    return False

# Tepi (u, v, w) untuk graf berarah dengan satu tepi berbobot negatif.
tepi = [(0, 1, 4), (0, 2, 2), (1, 3, 2), (2, 3, -3), (3, 4, 1), (4, 5, -2)]
n = 6

jarak = bellman_ford(tepi, n)
print("Jarak dari 0   :", jarak)
print("Siklus negatif :", ada_siklus_negatif(tepi, n, jarak))

# Tepi (5, 3, -1) menutup siklus 3 -> 4 -> 5 -> 3 dengan total bobot -2.
tepi_siklus = tepi + [(5, 3, -1)]
jarak_siklus = bellman_ford(tepi_siklus, n)
print("Dengan siklus  :", jarak_siklus)
print("Siklus negatif :", ada_siklus_negatif(tepi_siklus, n, jarak_siklus))

Jarak dari 0   : [0, 4, 2, -1, 0, -2]
Siklus negatif : False
Dengan siklus  : [0, 4, 2, -11, -8, -10]
Siklus negatif : True

Kasus pertama keluaran menunjukkan jarak negatif yang sah, yaitu simpul 3 dicapai dengan -1 lewat tepi (2, 3) berbobot -3. Kasus kedua justru menjatuhkan seluruh nilai ke angka yang tidak bermakna, karena siklus negatifnya dapat diputar berulang tanpa batas. Detektor berupa satu putaran pemeriksaan sederhana, dan itulah cara soal menanyakan keberadaan siklus negatif.

Soal untuk dipraktikkan#

Soal berikut dipilih agar setiap algoritma modul graf mendapat gilirannya, dari penelusuran kisi sampai heap berbobot. Kerjakan satu soal dengan lebih dari satu algoritma bila memungkinkan, karena perbandingan antar pendekatan memperjelas batas masing-masing.

1. network-delay-time : Dijkstra langsung pada graf berbobot, dengan tambahan syarat seluruh simpul harus tercapai.
2. min-cost-to-connect-all-points : memakai pola heap yang sama dengan Dijkstra untuk selalu mengambil sambungan termurah berikutnya.
3. rotting-oranges : BFS multi-sumber per menit, versi kisi dari penelusuran per level.
4. number-of-islands : menghitung komponen sel daratan dengan DFS atau BFS pada kisi.
5. number-of-connected-components-in-an-undirected-graph : menghitung komponen graf statis, cocok dibandingkan antara DFS dan union-find.
6. redundant-connection : tepi yang kedua ujungnya sudah satu himpunan adalah jawabannya, padanan union yang mengembalikan False.
7. course-schedule : deteksi siklus prasyarat dengan Kahn, memakai sisa simpul sebagai sinyalnya.

Ringkasan#

• Dijkstra memproses simpul berjarak terkecil lewat heap minimum dengan biaya $O(E \log V)$, dan hanya sah pada bobot tak negatif.
• Relaksasi adalah operasi dasarnya, dan array induk yang terisi saat relaksasi berhasil cukup untuk merekonstruksi lintasan.
• Bellman-Ford merelaksasi seluruh tepi V - 1 kali dengan biaya $O(V \cdot E)$ dan tetap benar pada bobot negatif.
• Tepi yang masih bisa merelaksasi setelah putaran terakhir menandakan siklus negatif.

Referensi#

• Dijkstra’s algorithm — Wikipedia : Algoritma Dijkstra, priority queue, dan syarat bobot tak negatif.
• Bellman–Ford algorithm — Wikipedia : Relaksasi berulang V - 1 kali dan deteksi siklus negatif.