0Pricing
Coding Interview Prep · Pelajaran

Algoritma Dijkstra dengan Antrean Prioritas

Implementasikan Dijkstra menggunakan heapq, telusuri langkah relaksasi pada graf berbobot, dan selesaikan masalah penerbangan termurah dengan paling banyak k pemberhentian

Algoritma Dijkstra dengan Antrean Prioritas adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Jalur Terpendek dalam Graf Berbobot

Algoritma Dijkstra menemukan jalur terpendek dari satu simpul sumber ke semua simpul lain dalam graf berbobot dengan bobot sisi non-negatif. Algoritma ini bekerja dengan memproses simpul secara rakus berdasarkan jarak terbaik yang diketahui saat ini—selalu memperluas simpul belum dikunjungi yang paling dekat. Struktur data kuncinya adalah tumpukan-min (antrean prioritas), yang secara efisien mengambil simpul dengan jarak terkecil.

Ikhtisar Langkah Algoritma

Algoritma Dijkstra: (1) Inisialisasikan dist[source] = 0 dan dist[all others] = inf. (2) Masukkan (0, source) ke dalam tumpukan-min. (3) Keluarkan simpul u dengan jarak terkecil. Jika simpul tersebut sudah dikunjungi dengan jarak yang lebih kecil, lewati. (4) Untuk setiap tetangga v dari u: jika dist[u] + weight(u,v) < dist[v], perbarui dist[v] dan masukkan (dist[v], v) ke dalam tumpukan. (5) Ulangi hingga tumpukan kosong.

Implementasi Python dengan heapq

heapq Python mengimplementasikan tumpukan-min. Kita merepresentasikan graf sebagai daftar ketetanggaan: graph[u] = [(v, weight), ...]. Tumpukan menyimpan tupel (distance, node). Kita menggunakan himpunan visited untuk melewati entri tumpukan yang sudah usang—entri yang dimasukkan sebelum jalur yang lebih baik ditemukan.

import heapq

def dijkstra(graph, source):
    n = len(graph)
    dist = [float('inf')] * n
    dist[source] = 0
    heap = [(0, source)]  # (distance, node)
    visited = set()
    
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        
        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(heap, (dist[v], v))
    
    return dist

Contoh yang Dikerjakan

Pertimbangkan graf dengan 5 simpul dan sisi: 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), 3→4 (3). Jalur terpendek dari simpul 0: ke 1 melalui 0→2→1 berbiaya 3, ke 2 berbiaya 1, ke 3 melalui 0→2→1→3 berbiaya 4, dan ke 4 melalui 0→2→1→3→4 berbiaya 7. Dijkstra menemukan semuanya dalam satu lintasan, bukan hanya jalur menuju satu sasaran.

import heapq

def dijkstra(graph, source):
    dist = [float('inf')] * len(graph)
    dist[source] = 0
    heap = [(0, source)]
    visited = set()
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

graph = [
    [(1,4),(2,1)],  # 0
    [(3,1)],         # 1
    [(1,2),(3,5)],   # 2
    [(4,3)],         # 3
    []               # 4
]
print(dijkstra(graph, 0))  # [0, 3, 1, 4, 7]

Alasan Dijkstra Gagal pada Bobot Negatif

Kebenaran algoritma Dijkstra bergantung pada fakta bahwa setelah sebuah simpul dikeluarkan dari heap minimum, jaraknya sudah pasti. Hal ini hanya berlaku jika bobot sisi tidak negatif. Dengan sisi negatif u→v berbobot -5, setelah mengunjungi v kita mungkin menemukan jalur melalui u yang lebih pendek—tetapi v sudah ditandai sebagai telah dikunjungi. Satu sisi negatif saja dapat membatalkan semua perhitungan jarak berikutnya.

Penerbangan Termurah dengan Maksimal K Pemberhentian (LeetCode 787)

Masalah ini menambahkan sebuah batasan: maksimal k pemberhentian. Dijkstra standar tidak menangani jumlah langkah secara bawaan. Solusinya adalah memperluas keadaan menjadi (cost, node, stops_remaining). Gunakan Dijkstra dengan tupel berisi tiga elemen ini, atau gunakan Bellman-Ford dengan k+1 putaran relaksasi. Dijkstra yang dimodifikasi berhenti ketika stops_remaining mencapai 0 sehingga lompatan lebih lanjut tidak dilakukan.

import heapq
from collections import defaultdict

def findCheapestPrice(n, flights, src, dst, k):
    graph = defaultdict(list)
    for u, v, w in flights:
        graph[u].append((v, w))
    
    heap = [(0, src, k + 1)]  # (cost, node, hops_left)
    visited = {}  # node -> min hops_left seen at this cost level
    
    while heap:
        cost, node, hops = heapq.heappop(heap)
        if node == dst:
            return cost
        if hops == 0:
            continue
        if visited.get(node, 0) >= hops:
            continue
        visited[node] = hops
        for nxt, w in graph[node]:
            heapq.heappush(heap, (cost + w, nxt, hops - 1))
    return -1

print(findCheapestPrice(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1))  # 200

Analisis Kompleksitas Waktu

Dengan heap biner, Dijkstra berjalan dalam O((V + E) log V) waktu: setiap simpul dikeluarkan sekali (V kali), setiap sisi dapat memicu penambahan elemen ke heap (E kali), dan setiap operasi heap memerlukan biaya O(log V). Dengan heap Fibonacci, batas tersebut meningkat menjadi O(E + V log V), tetapi heapq Python adalah heap biner. Untuk graf jarang (E ≈ V), versi heap biner memiliki kompleksitas O(V log V); untuk graf padat (E ≈ V²), kompleksitasnya adalah O(V² log V).

Merekonstruksi Jalur Terpendek

Untuk mendapatkan jalur sebenarnya, bukan hanya jaraknya, pertahankan array prev: saat memperbarui dist[v], tetapkan prev[v] = u. Setelah algoritma selesai, rekonstruksikan jalur dari sumber ke tujuan dengan menelusurinya mundur: mulai dari dst, ikuti penunjuk prev sampai mencapai source, lalu balik hasilnya.

import heapq

def dijkstra_path(graph, source, target):
    n = len(graph)
    dist = [float('inf')] * n
    prev = [-1] * n
    dist[source] = 0
    heap = [(0, source)]
    visited = set()
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited: continue
        visited.add(u)
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(heap, (dist[v], v))
    # Reconstruct
    path, node = [], target
    while node != -1:
        path.append(node)
        node = prev[node]
    return dist[target], path[::-1]

Menggunakan Dict untuk Graf Jarang

Jika simpul berupa string atau bilangan bulat yang tidak berurutan, gunakan defaultdict(list) untuk daftar ketetanggaan dan dict biasa untuk jarak. Hal ini umum dalam masalah LeetCode seperti Waktu Tunda Jaringan, yang simpulnya diberi label dari 1 sampai n. Ingatlah untuk menggunakan dist = {node: inf for node in all_nodes} dan memeriksa simpul yang tidak dapat dijangkau setelah algoritma selesai.

import heapq
from collections import defaultdict

def networkDelayTime(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    
    dist = {i: float('inf') for i in range(1, n+1)}
    dist[k] = 0
    heap = [(0, k)]
    
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    
    ans = max(dist.values())
    return ans if ans < float('inf') else -1

print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2))  # 2

Perbandingan dengan BFS untuk Graf Tak Berbobot

Untuk graf tak berbobot, BFS menemukan jalur terpendek dalam O(V + E)—lebih cepat daripada Dijkstra yang memiliki kompleksitas O((V+E) log V). Dijkstra menggeneralisasi BFS untuk graf berbobot dengan menggunakan antrean prioritas, bukan antrean FIFO biasa. Jika semua bobot sisi sama, Dijkstra berubah menjadi BFS. Pilih BFS untuk graf tak berbobot, Dijkstra untuk bobot non-negatif, dan Bellman-Ford untuk bobot negatif.

Dijkstra dengan Pengoptimalan Penurunan Kunci

Implementasi Dijkstra dalam buku teks menggunakan antrean prioritas dengan operasi penurunan-kunci: saat jarak sebuah simpul membaik, perbarui prioritasnya langsung di tempat. Cara ini memerlukan heap Fibonacci agar mencapai O(E + V log V), tetapi sulit diimplementasikan. Pendekatan penghapusan malas yang digunakan dalam wawancara justru menambahkan entri baru dan melewati pengambilan entri yang kedaluwarsa—lebih sederhana dengan tambahan biaya yang hanya berupa faktor konstan. Di Python, penghapusan malas dengan heapq adalah implementasi standar untuk wawancara.

Pemeriksaan Singkat

Ujilah pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.

Ringkasan Pelajaran

Dalam pelajaran ini, Anda mempelajari bahwa: Dijkstra menggunakan heap minimum untuk memproses simpul secara rakus berdasarkan urutan jarak terbaik saat ini, algoritma ini berjalan dalam O((V+E) log V) waktu dan gagal pada sisi berbobot negatif, dan entri heap yang kedaluwarsa ditangani dengan memeriksa himpunan simpul yang telah dikunjungi saat pengambilan. Berikutnya, kita membahas Bellman-Ford, yang menangani bobot negatif melalui n-1 putaran relaksasi.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Algoritma Dijkstra dengan Antrean Prioritas” gratis?

Ya — teks lengkap “Algoritma Dijkstra dengan Antrean Prioritas” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Algoritma Dijkstra dengan Antrean Prioritas”?

Implementasikan Dijkstra menggunakan heapq, telusuri langkah relaksasi pada graf berbobot, dan selesaikan masalah penerbangan termurah dengan paling banyak k pemberhentian Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?

Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.

Berapa lama pelajaran “Algoritma Dijkstra dengan Antrean Prioritas” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?

Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. Algoritma Dijkstra dengan Antrean Prioritas
  2. Bellman-Ford dan Siklus Negatif
  3. Floyd-Warshall: Jalur Terpendek Semua Pasangan
  4. Waktu Tunda Jaringan dan Rekonstruksi Jalur
← Kembali ke Coding Interview Prep