Wprowadzenie

Witaj ponownie w serii Algorytmy grafowe! Dijkstra jest szybki, ale zawodzi, gdy krawędzie mogą mieć ujemne wagi. Bellman-Ford obsługuje ujemne wagi i potrafi nawet wykryć, czy graf zawiera ujemny cykl.

Podobnie jak Dijkstra, wyznacza najkrótsze odległości od jednego źródła. Graf jest podany jako n (wierzchołki od 0 do n - 1) oraz edges — płaska tablica trójek [u0, v0, w0, ...] opisujących skierowane krawędzie u -> v o wadze w (wagi mogą być ujemne).

Nieosiągalne wierzchołki są oznaczane jako -1. Zaczynajmy!