Memilih Solusi Optimal

Tujuan (F12.2, elemen BK dan AP, Fase F): murid memilih dan menerapkan solusi terbaik dan paling efisien dengan struktur data yang tepat, misalnya rute terpendek atau penjadwalan. Target minimum: menelusuri Dijkstra dengan tangan pada graph kecil, lalu memakai program atau fungsi library yang tersedia. Target lanjutan: mengimplementasikan Dijkstra sendiri.

• Pertemuan 1 (2 JP): peta kota dari tali di lantai (lima kertas kota, tali berlabel km). Tonton Bagian 1 sampai segmen brute force dan greedy; diskusi "terbaik menurut apa".
• Pertemuan 2–3 (4 JP), Dijkstra dengan tangan: kartu jarak sementara di peta tali, trace table di kertas, Latihan 1. Ulangi pada graph buatan kelompok lain.
• Pertemuan 4 (2 JP), Python: tonton Bagian 2. Jalankan program contoh di bawah, ubah satu bobot (jalan macet), bandingkan rutenya.
• Pertemuan 5 (2 JP), penjadwalan: Latihan 2. Uji aturan greedy lain (paling singkat dulu, mulai paling awal dulu) dan cari contoh yang membuatnya gagal.
• Pertemuan 6–7 (4 JP), proyek mini: rute dari sekolah ke beberapa tempat di sekitarnya (jarak diukur sendiri atau fiktif), pilih solusi, tulis laporan perbandingan. Latihan 3. Lanjutan: menulis Dijkstra sendiri tanpa melihat contoh.

Program contoh (Python standar, tanpa instalasi tambahan):

import heapq

def dijkstra(graf, asal):
    jarak = {k: float("inf") for k in graf}
    dari = {}
    jarak[asal] = 0
    antre = [(0, asal)]
    while antre:
        d, kota = heapq.heappop(antre)
        if d > jarak[kota]:
            continue
        for tetangga, w in graf[kota].items():
            baru = d + w
            if baru < jarak[tetangga]:
                jarak[tetangga] = baru
                dari[tetangga] = kota
                heapq.heappush(antre, (baru, tetangga))
    return jarak, dari

graf = {"A": {"B": 2, "C": 5}, "B": {"A": 2, "C": 2, "D": 6},
        "C": {"A": 5, "B": 2, "D": 2, "E": 7},
        "D": {"B": 6, "C": 2, "E": 3}, "E": {"C": 7, "D": 3}}
print(dijkstra(graf, "A"))   # E = 9, rute A-B-C-D-E

Catatan: Dijkstra hanya benar untuk bobot yang tidak negatif. Aturan greedy "selesai paling awal" terbukti memberi jumlah kegiatan terbanyak; aturan greedy lain belum tentu.