Lewati ke konten utama
Numekara
Konsultasi GratisKontak

K1 · Modul 13

Graf 2: jalur terpendek dan pohon rentang

45 langkah singkat, dari mudah sampai tantangan.

  1. Level 1

    Kenal

  2. Level 2

    Paham

  3. Level 3

    Terapkan

  4. Level 4

    Tantangan

  5. Level 5

    Pendalaman

Intinya

  • Jalur terpendek berbobot dibangun dari relaksasi: perbaiki jarak[v] bila lewat u lebih pendek.
  • Dijkstra mengambil titik dengan jarak sementara terkecil dari heap: O((V + E) log V), benar hanya untuk bobot tidak negatif.
  • Bellman-Ford merelaksasi semua sisi V − 1 kali: O(V·E), menangani bobot negatif dan mendeteksi siklus negatif.
  • Union-find (gabung menurut ukuran + kompresi jalur) menjawab "apakah dua titik sudah tersambung?" hampir O(1).
  • Pohon rentang minimum: Kruskal (urutkan sisi + union-find) atau Prim (tumbuhkan dari satu titik dengan heap).

Sebelum mulai

±4–5 jam.

Modul ini memakai materi di bawah. Belum yakin? Ulas dulu bagian yang disebut.

Hasil belajar: menjalankan Dijkstra dengan heap, merekam rutenya, dan membuktikannya dengan invarian; menunjukkan kenapa bobot negatif membuatnya salah dan memakai Bellman-Ford untuk kasus itu; membangun union-find dengan gabung menurut ukuran dan kompresi jalur; menyusun pohon rentang minimum dengan Kruskal dan Prim; serta menganalisis waktu dan ruang setiap algoritma itu.

Proyek: Kurir Makmur langkah 13: rute_terpendek(graf, dari, ke) dengan Dijkstra dan jaringan_minimum(peta) dengan Kruskal + union-find (kontrak Proyek Kurir §3).

Istilah di modul ini (29)

Ketuk istilah untuk melihat penjelasannya. Di materi, istilah bergaris titik membuka kartu yang sama. Semua istilah course

Bahan modul

Semua kode, latihan, dan data modul ini dalam satu zip, untuk dijalankan di laptop atau Google Colab.

  • 28 contoh kode
  • 8 berkas latihan + tes
  • 1 berkas data
Semua data course (data-k1.zip) Cara menjalankan di laptop
Lihat isi zip
  • BACA-DULU.txt
  • kurir_dasar.py
  • contoh_k1_13_96.py
  • contoh_k1_13_117.py
  • contoh_k1_13_156.py
  • contoh_k1_13_186.py
  • contoh_k1_13_216.py
  • contoh_k1_13_317.py
  • contoh_k1_13_358.py
  • contoh_k1_13_427.py
  • contoh_k1_13_494.py
  • contoh_k1_13_521.py
  • contoh_k1_13_681.py
  • contoh_k1_13_732.py
  • contoh_k1_13_760.py
  • contoh_k1_13_808.py
  • contoh_k1_13_832.py
  • contoh_k1_13_896.py
  • contoh_k1_13_916.py
  • contoh_k1_13_1334.py
  • contoh_k1_13_1416.py
  • contoh_k1_13_1620.py
  • contoh_k1_13_1646.py
  • contoh_k1_13_1762.py
  • contoh_k1_13_1802.py
  • contoh_k1_13_1844.py
  • contoh_k1_13_2330.py
  • contoh_k1_13_2379.py
  • contoh_k1_13_2455.py
  • contoh_k1_13_2483.py
  • test_k1_13_1.py
  • test_k1_13_3.py
  • test_k1_13_4.py
  • test_k1_13_6.py
  • test_k1_13_2.py
  • test_k1_13_5.py
  • test_k1_13_7.py
  • test_k1_13_8.py
  • peta.json