Introduzione

Ti diamo di nuovo il benvenuto nella serie Algoritmi sui grafi! Finora tutti i nostri archi avevano lo stesso peso. Ora hanno un peso (un costo o una distanza) e vogliamo trovare il percorso più economico.

L'algoritmo di Dijkstra trova la distanza minima da una singola sorgente a ogni altro vertice in un grafo con pesi degli archi non negativi.

Un grafo pesato è rappresentato da n (vertici da 0 a n - 1) e da edges, un array piatto di terne [u0, v0, w0, u1, v1, w1, ...], in cui ogni terna rappresenta un arco diretto u -> v di peso w.

Cominciamo!