Introduction

¡Bienvenido de nuevo a la serie de Algoritmos de Grafos! Hasta ahora, todas nuestras aristas eran iguales. Ahora llevan un peso (un costo o distancia), y queremos la ruta más barata.

El Algoritmo de Dijkstra encuentra la distancia más corta desde una única fuente a todos los demás vértices en un grafo con pesos de arista no negativos.

Un grafo ponderado se da como n (vértices 0 a n - 1) y edges, un array plano de triplas [u0, v0, w0, u1, v1, w1, ...] donde cada tripla es una arista dirigida u -> v de peso w.

¡Comencemos!