Pengenalan

Selamat datang kembali di seri Algoritma Graf! Dijkstra cepat, tetapi tidak bisa digunakan ketika sisi memiliki bobot negatif. Bellman-Ford menangani bobot negatif, dan bahkan dapat memberi tahu kamu ketika sebuah graf memiliki siklus negatif.

Seperti Dijkstra, algoritma ini mencari jarak terpendek dari satu sumber. Graf diberikan sebagai n (simpul 0 hingga n - 1) dan edges, sebuah array datar berisi tripel [u0, v0, w0, ...] untuk sisi berarah u -> v dengan bobot w (bobot bisa negatif).

Simpul yang tidak dapat dijangkau dilaporkan sebagai -1. Mari kita mulai!