0Pricing
Competitive Programming Academy · Pelajaran

Dijkstra dengan Heap

Jalur terpendek greedy pada sisi non-negatif

Dijkstra dengan Heap adalah pelajaran Competitive Programming Academy 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 Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.

Masalah Jalur Terpendek

Anda ingin menemukan rute termurah dari satu simpul ke semua simpul lainnya. Dijkstra menyelesaikan masalah ini ketika setiap bobot sisi bernilai nol atau positif.

Gagasan Serakah

Dijkstra bersifat serakah: algoritme ini selalu memperluas simpul yang belum dikunjungi dengan jarak terkecil yang diketahui, dan menganggap jarak tersebut sudah final.

Mengapa Menggunakan Tumpukan Minimum

Untuk mengambil simpul terdekat dengan cepat, Anda memerlukan tumpukan minimum. Struktur ini memberikan jarak terkecil dalam waktu log n, bukan melalui pemindaian yang lambat.

import heapq

Mulai dengan Jarak

Atur setiap jarak menjadi tak hingga, lalu atur jarak sumber menjadi nol. Simpul yang belum dicapai akan tetap bernilai tak hingga.

dist = [float('inf')] * n
dist[src] = 0

Masukkan ke Tumpukan

Masukkan sumber sebagai sebuah tupel berisi (jarak, simpul). Menempatkan jarak di posisi pertama memungkinkan tumpukan mengurutkan entri berdasarkan biaya secara otomatis.

pq = [(0, src)]

Ambil Simpul Terdekat

Pada setiap perulangan, ambil nilai terkecil (d, u). Nilai d tersebut adalah jarak terpendek ke u, sehingga pemrosesan u selesai setelah diambil.

d, u = heapq.heappop(pq)

Lewati Entri Usang

Sebuah simpul dapat berada di dalam tumpukan dengan jarak lama yang lebih besar. Lewati entri tersebut ketika d lebih besar daripada jarak yang tersimpan.

if d > dist[u]:
    continue

Relaksasikan Tetangga

Relaksasi berarti mencoba memperbaiki jarak tetangga: jika melalui u lebih murah, perbarui jaraknya lalu masukkan simpul tersebut.

if d + w < dist[v]:
    dist[v] = d + w
    heapq.heappush(pq, (dist[v], v))

Trik Penghapusan Tertunda

Tumpukan Python tidak dapat memperbarui kunci, jadi Anda memasukkan duplikat dan mengabaikan entri yang usang. Gaya tertunda ini membuat kode tetap singkat dan cepat.

Waktu Berjalan

Dengan tumpukan biner, Dijkstra berjalan dalam O((V + E) log V). Kompleksitas ini dengan mudah menangani graf dengan ratusan ribu sisi.

Perhatikan Bobot Sisi

Dijkstra gagal pada sisi negatif, karena jarak yang diambil mungkin belum final. Untuk kasus tersebut, gunakan Bellman-Ford.

Pemeriksaan Singkat

Anda mengambil (d, u), tetapi d lebih besar daripada dist[u]. Apa yang harus Anda lakukan?

Rekapitulasi: Dijkstra dengan Tumpukan

Anda menginisialisasi jarak, memasukkan (dist, node), mengambil simpul terdekat, melewati pengambilan yang usang, lalu merelaksasikan tetangga. Itulah Dijkstra dalam O((V+E) log V). 🚀

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Dijkstra dengan Heap” gratis?

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

Apa yang akan aku pelajari di “Dijkstra dengan Heap”?

Jalur terpendek greedy pada sisi non-negatif Kamu berlatih Competitive Programming Academy 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 Competitive Programming Academy?

Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy 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 “Dijkstra dengan Heap” 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 Competitive Programming Academy ini?

Ya. Setiap pelajaran Competitive Programming Academy 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. Dijkstra dengan Heap
  2. 0-1 BFS dengan Deque
  3. Bellman-Ford & Sisi Negatif
  4. Floyd-Warshall untuk Semua Pasangan
← Kembali ke Competitive Programming Academy