Introduction

Bienvenue dans la suite de la série sur les Algorithmes de Graphes ! Jusqu'à présent, nos arêtes étaient toutes égales. Maintenant, elles portent un poids (un coût ou une distance), et nous voulons l'itinéraire le moins cher.

L'Algorithme de Dijkstra trouve la distance la plus courte entre une source unique et tous les autres sommets d'un graphe avec des poids d'arêtes non négatifs.

Un graphe pondéré est donné sous la forme de n (sommets de 0 à n - 1) et edges, un tableau plat de triplets [u0, v0, w0, u1, v1, w1, ...] où chaque triplet est une arête orientée u -> v de poids w.

Commençons !