All-Pairs Shortest Path

Saat kuliah Desain dan Analisis Algoritma (yang diampu oleh Kak Raja), kami diberikan tugas akhir untuk menjelaskan satu topik algoritma tingkat advanced. Seingat saya untuk pembagian topiknya diundi. Untungnya tim kami (+Norman, +Reynaldo, +Windi) dapat bagian yang termasuk paling mudah (All-pairs shortest path), yang lain seingat saya dapat yang lebih sulit seperti Flow, Fast fourier transform, dan Shor’s algorithm?

Jadinya kami mengambil sumber dari buku Algorithms dari Jeff Erickson (Bukunya gratis). Buku tsb juga menjadi salah satu buku referensi saat kuliah. Daripada slide dan diktatnya nganggur, jadi saya taro sini saja biar enggak mubazir. Lumayan untuk nambah sumber belajar CS berbahasa Indonesia.

Biasanya untuk APSP kita pakai algoritma Floyd-Warshall, namun notes di bawah juga membantu menjelaskan perspektif lain yang tidak biasa didengar (buat saya) seperti algoritma Johnson, Shimbel, dan Fischer-Meyer

Materi

Slide

Slide bisa diunduh disini.

Diktat

Diktat bisa diunduh disini.