GraphsLanjutFase E–FE1E5

DIJKSTRA'S ALGORITHM / A* SEARCH

Video ini membandingkan dua algoritma pencari jalur terpendek pada labirin yang sama: Dijkstra dan A* Search. Dijkstra menjelajah ke segala arah berdasarkan jarak sejauh ini, sedangkan A* memakai heuristik untuk mengarah ke tujuan sehingga umumnya mengunjungi lebih sedikit sel. Visualisasi menampilkan kedua penelusuran berdampingan dengan hitungan cells visited sebagai ukuran efisiensi.

Example use case

Membandingkan mesin routing peta digital untuk memilih algoritma tercepat saat menghitung rute pengantaran ojek online.

Syllabus

Membandingkan algoritma pencari jalur berdampingan di labirin yang sama menunjukkan kapan tiap algoritma paling cocok dipakai.

Objectives

·Memahami perbedaan cara BFS, Dijkstra, dan A* menjelajahi peta
·Menjelaskan kapan bobot dan heuristik memengaruhi pilihan algoritma
·Menerapkan perbandingan untuk memilih algoritma rute yang tepat

How It Works

·Jalankan dua algoritma pada labirin identik secara bersamaan
·BFS optimal saat semua langkah berbobot sama
·Dijkstra menimbang biaya tiap jalur, cocok untuk graf berbobot
·A* menambah heuristik agar pencarian mengarah ke tujuan
·Bandingkan jumlah sel yang dikunjungi dan total biaya sebagai ukuran efisiensi

Prerequisites

·Breadth-First Search
·Dijkstra
·A* Search

Real-World Uses

·Memilih BFS atau Dijkstra untuk peta game tergantung biaya tiap petak
·Menentukan mesin rute tercepat untuk pengantaran ojek online
·Menguji algoritma navigasi mana yang paling hemat untuk aplikasi maps

Complexity BFS O(V+E); Dijkstra O((V+E) log V); A* O(E) terarah