Introduzione

Bentornato alla serie Graph Algorithms! Dijkstra è veloce, ma non funziona quando gli archi possono essere negativi. Bellman-Ford gestisce pesi negativi e può persino dirti quando un grafo ha un ciclo negativo.

Come Dijkstra, trova le distanze minime da un'unica sorgente. Il grafo è dato come n (vertici da 0 a n - 1) e edges, un array lineare di terne [u0, v0, w0, ...] per gli archi orientati u -> v di peso w (i pesi possono essere negativi).

I vertici irraggiungibili vengono indicati con -1. Cominciamo!