Introduction

¡Bienvenido de nuevo a la serie de Algoritmos de Grafos! Dijkstra es rápido, pero falla cuando las aristas pueden ser negativas. Bellman-Ford maneja pesos negativos e incluso puede decirte cuándo un grafo tiene un ciclo negativo.

Al igual que Dijkstra, encuentra las distancias más cortas desde una única fuente. El grafo se proporciona como n (vértices 0 a n - 1) y edges, un array plano de triplas [u0, v0, w0, ...] para aristas dirigidas u -> v de peso w (los pesos pueden ser negativos).

Los vértices inalcanzables se reportan como -1. ¡Empecemos!