Proyek: Pencari Jalur Terpendek

Pathfinding adalah salah satu aplikasi Dijkstra yang paling konkret: game RTS mencari rute unit, GPS mencari jalur tercepat, dan robot mencari jalan bebas rintangan. Pada proyek ini, kita membangun pathfinder pada grid 2D dengan rintangan. Setiap sel adalah node graph; setiap sel yang dapat dilalui terhubung ke empat tetangga (atas, bawah, kiri, kanan) dengan bobot 1. Dijkstra dengan std::priority_queue menjadi mesin pencari, dan array parent menyimpan jejak untuk rekonstruksi jalur.

Tool yang akan kita bangun memiliki cakupan berikut:

• menerima grid 2D berisi karakter . (dapat dilalui), # (rintangan), S (start), G (goal),
• memodelkan grid sebagai graph berbobot dengan bobot seragam 1,
• menjalankan Dijkstra dengan std::priority_queue min-heap,
• merekonstruksi jalur dari start ke goal via parent array,
• mencetak grid dengan jalur ditandai karakter *,
• menangani kasus tidak ada jalur dengan pesan yang jelas.

Tampilan Akhir Tool #

Berikut contoh input grid dan output dengan jalur yang ditemukan:

Input:
.....
.###.
.S.#.
...#.
...G.

Jalur terpendek (panjang=4):
.....
.###.
.S*#.
..*#.
..*G.

Bintang * menandai jalur dari S ke G sepanjang 4 langkah (tidak termasuk start, termasuk goal). Pada Bagian 4 kita menguji kasus tanpa rintangan, dengan rintangan, dan dead end.

Tujuan Pembelajaran #

Setelah menyelesaikan proyek ini, kita mampu:

• memodelkan grid 2D sebagai graph berbobot (node = sel, edge = pasangan sel tetangga),
• mengimplementasikan Dijkstra dengan std::priority_queue min-heap dan lazy deletion,
• menyimpan jejak parent untuk rekonstruksi jalur,
• menguji edge case: jalur tunggal, banyak jalur sama panjang, tidak ada jalur,
• mencetak grid hasil dengan jalur ditandai.

Prasyarat #

Proyek ini memanfaatkan materi yang sudah dibahas pada Section sebelumnya:

• Dijkstra — algoritma inti yang diimplementasikan,
• Graph Representation — adjacency list sebagai dasar pemodelan,
• Priority Queue dan Heap — std::priority_queue dengan std::greater,
• Breadth-First Search — konsep traversal serupa untuk bobot seragam,
• STL Containers — std::vector, std::pair.

Tahapan Pengerjaan #

Proyek dikerjakan dalam empat bagian berurutan:

1. Bagian 1: Pemodelan Graph — merepresentasikan grid 2D sebagai graph berbobot.
2. Bagian 2: Implementasi Dijkstra — menulis algoritma Dijkstra dengan priority queue.
3. Bagian 3: Rekonstruksi Jalur — melacak parent array untuk menampilkan jalur.
4. Bagian 4: Pengujian Jalur — menguji berbagai skenario: rintangan, dead end, multiple goals.

Mulailah dari Bagian 1 dan kerjakan secara berurutan. Setiap bagian membangun di atas berkas bagian sebelumnya.