Wawancara Koding: Mengimplementasikan Algoritma Jalur Terpendek Dijkstra

Prompt dan Cakupan

Anda diberikan graf berarah dengan n simpul yang diberi label 0 hingga n - 1. Setiap edge berupa tuple (from, to, weight). Diberikan source dan target, kembalikan pasangan yang berisi jarak terpendek dan satu jalur terpendek dari source ke target. Kembalikan (-1, []) jika target tidak dapat dijangkau.

Untuk versi ini, asumsikan 1 <= n <= 100000, 0 <= m <= 300000, setiap label simpul valid, dan 0 <= weight <= 10^9. Edge paralel, edge berbobot nol, dan self-loop diperbolehkan. source dan target adalah label yang valid. Jika keduanya sama, kembalikan (0, [source]). Jalur terpendek mana pun dapat diterima jika terdapat beberapa jalur dengan jarak yang sama.

Sebagai contoh, dengan edge (0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5), (3, 4, 3), dan (2, 4, 12), jawaban dari 0 ke 4 adalah jarak 7 dan jalur [0, 2, 1, 3, 4].

Kondisi bobot non-negatif merupakan bagian dari kontrak algoritma. Graf berbobot tidak serta-merta mengindikasikan penggunaan Dijkstra: graf tanpa bobot lebih cocok menggunakan BFS, DAG dapat menggunakan pemrograman dinamis topologis, dan graf umum dengan edge negatif membutuhkan algoritma seperti Bellman-Ford.

Apa yang Dinilai oleh Pewawancara

Sinyal pertama adalah pemilihan algoritma berdasarkan kontrak masalah. Dijkstra cocok karena bobot edge bernilai non-negatif dan hanya melibatkan satu source. Kandidat yang menyatakan "graf berbobot berarti Dijkstra" tanpa menanyakan tentang edge negatif telah melewatkan prasyarat yang menentukan.

Sinyal kedua adalah invarian struktur data. Adjacency matrix akan membutuhkan ruang O(V^2), yang tidak cocok untuk hingga 100.000 simpul. Adjacency list hanya menyimpan informasi V + E yang digunakan dalam penelusuran. Min-heap mengambil simpul yang belum diselesaikan (unsettled) dengan jarak terkecil yang telah ditemukan.

Sinyal ketiga adalah bagaimana penurunan jarak direpresentasikan. heapq pada Python tidak memperbarui elemen arbitrer secara in-place. Solusi praktisnya adalah memasukkan (push) pasangan (distance, node) baru dan kemudian melewati (skip) pasangan lama saat jaraknya tidak lagi sama dengan distances[node]. Detail lazy-deletion ini mudah terlewatkan dan memengaruhi penalaran kebenaran serta batas kompleksitas yang tepat.

Pewawancara juga mengharapkan pembuktian, bukan sekadar kode yang berfungsi. Jawaban yang kuat menjelaskan mengapa entri terkini pertama yang di-pop untuk suatu simpul bersifat final, mengapa bobot non-negatif membuat langkah greedy tersebut aman, dan mengapa target dapat dikembalikan saat di-pop dan bukan saat pertama kali ditemukan. Rekonstruksi jalur, input yang tidak dapat dijangkau, edge berbobot nol, edge paralel, batas lebar integer, dan pengujian adversarial melengkapi jawaban tersebut.

Pertanyaan Klarifikasi Sebelum Menjawab

• Apakah bobot edge bisa bernilai negatif? Pada masalah dasar, jawabannya tidak. Jika edge negatif diperbolehkan,

pembuktian penyelesaian (settling proof) dan early exit pada Dijkstra tidak lagi berlaku.

• Apakah graf ini berarah? Ya. Untuk graf tak berarah, tambahkan kedua arah ke dalam adjacency list.
• Apakah kita hanya membutuhkan jaraknya saja atau juga jalurnya? Versi ini membutuhkan keduanya, jadi simpan predecessor

setiap kali relaksasi memberikan perbaikan jarak yang lebih baik secara ketat (strictly improves).

• Apakah boleh ada edge paralel, edge berbobot nol, atau self-loop? Ya. Proses relaksasi menanganinya

tanpa prapemrosesan. Self-loop non-negatif tidak dapat memperbaiki simpulnya sendiri.

• Apa yang harus dikembalikan jika tidak terjangkau? Kembalikan (-1, []); jangan keliru menganggapnya sebagai jalur dengan panjang nol.
• Ketika ada beberapa jalur terpendek, apakah salah satu saja dapat diterima? Ya. Implementasi hanya memperbarui

predecessor pada perbaikan ketat, sehingga alternatif dengan bobot sama tidak mengubah struktur pohon jalur.

• Seberapa besar jarak yang dapat terbentuk? Jalur terpendek sederhana memiliki paling banyak n - 1 edge, sehingga di bawah

batasan yang ditentukan nilainya berada di bawah 10^14. Integer pada Python tidak memiliki batas; gunakan integer 64-bit pada bahasa dengan tipe data fixed-width.

Kerangka Jawaban 30 Detik

"Saya akan membangun adjacency list dan menyimpan distances[v], jarak source-ke-v terbaik yang ditemukan sejauh ini. Saya menginisialisasi source ke nol dan memasukkan (0, source) ke dalam min-heap. Setiap kali saya melakukan pop pada entri terkecil, saya akan melewatinya jika entri tersebut sudah basi (stale). Jika tidak, jarak simpul tersebut bersifat final karena setiap edge yang tersisa memiliki bobot non-negatif. Saya merelaksasi setiap edge keluar dan melakukan push entri heap baru untuk setiap perbaikan jarak secara ketat, mencatat predecessor untuk rekonstruksi jalur. Saya dapat berhenti saat entri terkini dari target di-pop. Jika jaraknya tetap tak hingga, saya mengembalikan (-1, []); jika tidak, saya menelusuri predecessor ke belakang dan membalik jalurnya. Dengan lazy heap entries, kompleksitas waktu adalah O((V + E) log E) dan ruang adalah O(V + E)."

Pembahasan Mendalam Langkah Demi Langkah

Mulailah dengan memisahkan antara rute yang baru ditemukan dan rute terpendek yang sudah terbukti. distances[v] adalah batas atas dari jarak terpendek yang sebenarnya karena nilainya berupa tak hingga atau panjang dari rute nyata yang telah ditemukan. Merelaksasi edge u -> v dengan bobot w menguji apakah rute melalui u lebih baik: distances[u] + w < distances[v]. Perbaikan yang lebih baik secara ketat akan memperbarui jarak serta previous[v].

Heap dapat memuat beberapa entri untuk simpul yang sama. Pada contoh, edge 0 -> 1 pertama-tama memasukkan jarak 4. Setelah simpul 2 diproses, rute 0 -> 2 -> 1 memperbaiki simpul 1 menjadi berjarak 3 dan memasukkan entri kedua. Saat (4, 1) akhirnya di-pop, 4 != distances[1], sehingga entri tersebut basi dan harus diabaikan. Tidak diperlukan penghapusan elemen heap secara eksplisit maupun set penanda simpul yang sudah dikunjungi (visited set).

from heapq import heappop, heappush


def shortest_path(
    n: int,
    edges: list[tuple[int, int, int]],
    source: int,
    target: int,
) -> tuple[int, list[int]]:
    graph: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for node, neighbor, weight in edges:
        if weight < 0:
            raise ValueError("Dijkstra requires non-negative edge weights")
        graph[node].append((neighbor, weight))

    distances = [float("inf")] * n
    previous = [-1] * n
    distances[source] = 0
    heap: list[tuple[int, int]] = [(0, source)]

    while heap:
        distance, node = heappop(heap)
        if distance != distances[node]:
            continue
        if node == target:
            break

        for neighbor, weight in graph[node]:
            candidate = distance + weight
            if candidate < distances[neighbor]:
                distances[neighbor] = candidate
                previous[neighbor] = node
                heappush(heap, (candidate, neighbor))

    if distances[target] == float("inf"):
        return -1, []

    path = []
    node = target
    while node != -1:
        path.append(node)
        node = previous[node]
    path.reverse()
    return int(distances[target]), path

Argumen kebenaran memiliki dua bagian. Pertama, setiap nilai berhingga dalam distances adalah panjang dari jalur nyata yang ditemukan, sehingga nilainya tidak mungkin lebih kecil dari jarak jalur terpendek sebenarnya. Kedua, andaikan entri terkini untuk u di-pop tetapi terdapat jalur yang lebih pendek menuju u. Pada jalur tersebut, ambil simpul pertama yang belum diselesaikan (unsettled) dan sebut predecessor-nya sebagai x. Simpul x telah diselesaikan sebelumnya, sehingga edge keluarnya telah direlaksasi. Oleh karena itu, simpul unsettled pertama menerima heap key yang tidak lebih besar dari panjang jalur hipotetis yang lebih pendek ke u. Karena semua bobot edge yang tersisa non-negatif, key tersebut lebih kecil daripada key yang di-pop untuk u dan seharusnya di-pop lebih dulu—sebuah kontradiksi. Dengan demikian, jarak terkini yang di-pop adalah final.

Bukti ini juga mendefinisikan titik early-exit yang aman. Berhentilah hanya setelah target di-pop dengan jarak terkini yang bukan entri basi. Jangan berhenti saat sebuah edge pertama kali menemukan target: rute berikutnya mungkin memberikan hasil yang lebih baik. Untuk graf contoh, penemuan langsung simpul 4 berbiaya 13, sedangkan rute final berbiaya 7.

previous[v] = u mencatat edge terakhir dari jalur terbaik saat ini menuju v. Begitu jarak target bersifat final, menelusuri predecessor pasti akan mencapai source karena setiap penugasan predecessor berasal dari rute nyata yang berakar di source. Membalik rantai tersebut menghasilkan urutan jalur dari awal ke akhir. Ketika source sama dengan target, source langsung di-pop dan rekonstruksi mengembalikan [source].

Membangun adjacency list membutuhkan ruang O(V + E) dan waktu O(E). Setiap relaksasi yang berhasil akan melakukan push satu entri ke heap, sehingga terdapat paling banyak E operasi push di luar entri awal source. Dengan duplikat lazy, heap dapat memuat O(E) entri, menghasilkan waktu O((V + E) log E) dan total ruang O(V + E). Buku teks sering menyebutkan O((V + E) log V) untuk heap yang mendukung decrease-key, atau menyederhanakannya ke batas tersebut untuk graf jarang yang sederhana. Menyebutkan batas log E untuk implementasi lazy lebih tepat.

Ujilah kontrak masalahnya, bukan hanya kasus ideal (happy path). Contoh yang diberikan harus mengembalikan (7, [0, 2, 1, 3, 4]). Edge paralel dan bobot nol—(0, 1, 10), (0, 1, 2), (1, 2, 0)—harus mengembalikan (2, [0, 1, 2]). Uji juga target yang tidak terjangkau, source yang sama dengan target, self-loop, alternatif dengan biaya sama, dan edge dengan bobot nol. Edge negatif harus memicu error secara eksplisit dan bukannya menghasilkan jawaban secara diam-diam di bawah prasyarat yang dilanggar.

Pengujian diferensial kecil dapat menghasilkan graf non-negatif secara acak, menjalankan fungsi ini dari setiap source, dan membandingkan jaraknya dengan Bellman-Ford. Untuk jalur yang dikembalikan, verifikasi simpul pertama dan terakhir, verifikasi bahwa setiap pasangan berurutan merupakan edge input yang valid, dan jumlahkan bobot edge yang dipilih. Pada edge paralel, pengujian harus mengaitkan langkah jalur dengan bobot edge yang sesuai alih-alih mengasumsikan setiap pasangan simpul hanya memiliki satu edge.

Contoh Jawaban Berkualitas Tinggi

"Pertama-tama, saya akan mengonfirmasi bahwa semua bobot edge bernilai non-negatif, graf berarah, dan jalur terpendek mana pun dapat diterima. Kondisi tersebut memungkinkan saya menggunakan Dijkstra. Saya akan menyimpan edge keluar dalam sebuah adjacency list karena graf dapat memiliki 100.000 simpul dan 300.000 edge; adjacency matrix akan memakan memori terlalu besar.

distances[v] berawal dari tak hingga kecuali untuk source, yang berawal dari nol. Min-heap menyimpan pasangan (distance, node) yang ditemukan. Ketika saya menemukan rute yang lebih pendek melalui simpul saat ini, saya memperbarui jarak dan predecessor tetangga serta melakukan push pasangan baru. Karena heapq tidak memiliki operasi arbitrary decrease-key, pasangan lama tetap berada di heap. Saya mendeteksinya dengan membandingkan jarak yang di-pop dengan nilai pada array saat ini dan melewati setiap ketidakcocokan.

Bukti kuncinya adalah invarian penyelesaian (settling invariant). Ketika entri terkini untuk simpul u menjadi nilai minimum pada heap, setiap hipotesis rute yang lebih pendek akan memuat simpul unsettled pertama yang predecessor-nya telah diselesaikan. Relaksasi dari predecessor tersebut akan menempatkan jarak prefix yang sama atau lebih kecil ke dalam heap. Bobot sisa yang non-negatif berarti prefix tersebut seharusnya sudah di-pop sebelum u, yang merupakan sebuah kontradiksi. Oleh karena itu, u bersifat final. Inilah mengapa saya boleh berhenti saat entri terkini target di-pop, tetapi tidak saat target pertama kali terlihat.

Jika target tetap tak hingga, saya mengembalikan (-1, []). Jika tidak, saya menelusuri pointer predecessor dari target ke source dan membaliknya. Setiap relaksasi yang berhasil menghasilkan paling banyak satu entri heap baru, sehingga implementasi lazy ini berjalan dalam waktu O((V + E) log E) dan menggunakan ruang O(V + E). Pada bahasa dengan tipe fixed-width, saya akan menggunakan tipe 64-bit untuk jarak. Saya akan menguji entri basi, edge paralel dan berbobot nol, jalur dengan biaya yang sama, source sama dengan target, input yang tidak terjangkau, dan penolakan terhadap edge negatif."

Kesalahan Umum

• Menjalankan Dijkstra tanpa menanyakan tentang bobot negatif → bukti finalisasi greedy menjadi tidak berlaku →

Jadikan bobot non-negatif sebagai prasyarat eksplisit dan tolak input yang tidak valid.

• Berhenti saat target pertama kali direlaksasi → rute pertama yang ditemukan mungkin lebih mahal →

Berhentilah hanya saat entri heap terkini dari target di-pop.

• Memproses entri heap yang basi → jarak lama akan memindai edge keluar berulang kali → **Lewati ketika

distance != distances[node].**

• Menandai simpul sebagai visited saat pertama kali di-push → rute lebih pendek yang ditemukan kemudian akan terhalang → **Sebuah simpul

hanya dianggap settled saat entri minimum terkini miliknya di-pop.**

• Menggunakan adjacency matrix → input yang jarang (sparse) menghabiskan memori O(V^2) → **Gunakan adjacency list dengan

penyimpanan O(V + E).**

• Memperbarui predecessor pada jarak yang sama tanpa aturan tie-breaking → siklus berbobot nol dapat mengubah-ubah pilihan

jalur tanpa henti → Gunakan perbaikan ketat (strict improvement) jika jalur terpendek mana pun dapat diterima.

• Mengembalikan jarak berhingga tetapi tanpa kontrak jalur → implementasi gagal memenuhi prompt

→ Catat predecessor pada setiap perbaikan ketat dan rekonstruksi setelah pencarian selesai.

• Menyebut implementasi heap ini sebagai O(E log V) tanpa kualifikasi → duplikasi lazy dapat membuat

ukuran heap proporsional terhadap E → **Sebutkan batas O((V + E) log E), lalu jelaskan batas decrease-key konvensional.**

• Menggunakan jarak 32-bit → total jarak jalur dapat melebihi sekitar 2,1 miliar → **Gunakan integer Python atau tipe

64-bit.**

• Hanya menguji jarak akhir → rantai predecessor yang salah bentuk tidak akan terdeteksi → **Validasi

juga titik ujung jalur, edge, dan total penjumlahan bobot.**

Pertanyaan Lanjutan dan Cara Menanganinya

Lanjutan 1: Apa yang berubah jika hanya jarak yang diperlukan?

Hapus array previous dan logika rekonstruksi jalur. Pencarian, pembuktian, dan batas asimtotik tetap sama, meskipun penyimpanan simpul tambahan berkurang sebanyak satu array O(V). Early exit saat pop terkini pada target tetap aman dilakukan.

Lanjutan 2: Bagaimana jika kita membutuhkan jarak terpendek dari setiap source?

Menjalankan Dijkstra dari setiap simpul membutuhkan biaya O(V(V + E) log E) dengan implementasi ini. Untuk graf padat (dense), Floyd-Warshall menggunakan waktu O(V^3) dan ruang O(V^2) serta dapat menangani edge negatif selama tidak ada siklus negatif. Algoritma Johnson menggabungkan reweighting dengan pemanggilan Dijkstra berulang untuk graf jarang dengan edge negatif tanpa siklus negatif. Pilihlah berdasarkan kepadatan graf dan volume kueri yang sebenarnya.

Lanjutan 3: Bagaimana jika edge negatif diperbolehkan?

Gunakan Bellman-Ford untuk graf berarah umum. Algoritma ini merelaksasi semua edge secara berulang, berjalan dalam waktu O(VE), dan relaksasi tambahan yang berhasil akan mendeteksi siklus negatif yang dapat dijangkau. Contoh kasus 0 -> 1 = 2, 0 -> 2 = 5, 2 -> 1 = -10 memperlihatkan masalah ini: Dijkstra dengan early-exit menyelesaikan target 1 pada nilai 2, padahal rute sebenarnya melalui simpul 2 berbiaya -5.

Lanjutan 4: Bagaimana jika graf berupa DAG dan beberapa edge bernilai negatif?

Lakukan topological sort pada DAG, kemudian relaksasi edge keluar sekali saja sesuai urutan topologis. Setiap predecessor diproses sebelum successor-nya, sehingga bobot negatif aman digunakan dan total waktu yang dibutuhkan adalah O(V + E). Cara ini mengungguli Bellman-Ford dan Dijkstra di bawah kontrak asiklik yang lebih ketat.

Lanjutan 5: Bagaimana jika setiap bobot bernilai 0 atau 1?

Gunakan 0-1 BFS dengan deque. Lakukan push relaksasi berbobot nol ke depan (front) dan relaksasi berbobot satu ke belakang (back). Deque mempertahankan urutan jarak yang tidak menurun (nondecreasing), menghasilkan waktu O(V + E) tanpa memerlukan heap.

Lanjutan 6: Bagaimana pembaruan edge yang sering akan mengubah desain?

Untuk pembaruan yang jarang, bangun ulang adjacency list atau ubah edge yang terdampak lalu jalankan ulang Dijkstra; solusi sederhana adalah yang paling mudah diverifikasi. Pembaruan yang sering dengan persyaratan latensi ketat membutuhkan teknik dynamic shortest-path atau caching pohon source dengan mekanisme invalidasi, yang nilainya bergantung pada rasio update/query dan struktur graf. Jangan mengklaim bahwa perubahan edge lokal hanya memengaruhi kedua titik ujungnya saja.

Lanjutan 7: Bagaimana cara mengembalikan jalur terpendek terkecil secara leksikografis?

Perbandingan jarak ketat saja tidak cukup karena secara sengaja mempertahankan jalur pertama yang berbiaya sama. Tentukan kontrak pengurutannya terlebih dahulu. Salah satu pendekatan adalah menghitung jarak terpendek, membatasi kandidat transisi hanya pada edge yang konsisten dengan jarak tersebut, lalu memilih simpul berikutnya terkecil yang valid sambil memastikan target tetap dapat dijangkau. Siklus berbobot nol membutuhkan penanganan yang sadar siklus (cycle-aware). Membandingkan tuple jalur lengkap di dalam setiap entri heap lebih sederhana untuk input kecil tetapi dapat menambah biaya penyalinan dan perbandingan yang signifikan.