Introduction

Willkommen zurück zur Graph-Algorithmen-Serie! Dijkstra ist schnell, aber er scheitert, wenn Kanten negativ sein können. Bellman-Ford verarbeitet negative Gewichte und kann Ihnen sogar sagen, wenn ein Graph einen negativen Zyklus hat.

Wie Dijkstra findet er die kürzesten Entfernungen von einer einzelnen Quelle. Der Graph ist gegeben als n (Knoten 0 bis n - 1) und edges, ein flaches Array von Tripeln [u0, v0, w0, ...] für gerichtete Kanten u -> v mit dem Gewicht w (Gewichte können negativ sein).

Unerreichbare Knoten werden als -1 gemeldet. Fangen wir an!