Pengantar

Selamat datang kembali di seri Algoritma Graf! Sejauh ini semua edge kita memiliki bobot yang sama. Sekarang edge memiliki bobot (biaya atau jarak), dan kita ingin rute termurah.

Algoritma Dijkstra menemukan jarak terpendek dari satu sumber ke setiap vertex lain dalam graf dengan bobot edge non-negatif.

Graf berbobot diberikan sebagai n (vertex 0 hingga n - 1) dan edges, sebuah array datar berisi tripel [u0, v0, w0, u1, v1, w1, ...], dengan setiap tripel merupakan edge berarah u -> v berbobot w.

Mari kita mulai!