Introduction

Welcome back to the Graph Algorithms series! Dijkstra is fast, but it breaks when edges can be negative. Bellman-Ford handles negative weights, and it can even tell you when a graph has a negative cycle.

Like Dijkstra, it finds shortest distances from a single source. The graph is given as n (vertices 0 to n - 1) and edges, a flat array of triples [u0, v0, w0, ...] for directed edges u -> v of weight w (weights may be negative).

Unreachable vertices are reported as -1. Let's get started!