Introduction

Bem-vindo de volta à série de Algoritmos de Grafos! O Dijkstra é rápido, mas ele falha quando as arestas podem ser negativas. O Bellman-Ford lida com pesos negativos e pode até informar quando um grafo possui um ciclo negativo.

Assim como o Dijkstra, ele encontra as distâncias mais curtas a partir de uma única origem. O grafo é fornecido como n (vértices de 0 a n - 1) e edges, um array plano de triplas [u0, v0, w0, ...] para arestas direcionadas u -> v de peso w (os pesos podem ser negativos).

Vértices inalcançáveis são reportados como -1. Vamos começar!