Introduction

Bienvenue dans la suite de la série sur les Algorithmes de Graphes ! Dijkstra est rapide, mais il échoue lorsque les arêtes peuvent être négatives. Bellman-Ford gère les poids négatifs, et il peut même vous indiquer quand un graphe possède un cycle négatif.

Comme Dijkstra, il trouve les distances les plus courtes à partir d'une source unique. Le graphe est donné sous la forme de n (sommets de 0 à n - 1) et edges, un tableau plat de triplets [u0, v0, w0, ...] pour les arêtes orientées u -> v de poids w (les poids peuvent être négatifs).

Les sommets inaccessibles sont signalés par -1. C'est parti !