OIA-Wiki

Dado un grafo con aristas con longitudes positivas, y un nodo de “comienzo” (al cual llamaremos source por la definición en inglés, o S para resumir), encontrar el camino más corto desde éste nodo hasta todos los demás.

Comentario: la idea de nombrar a algunas cosas según su significado en inglés es que en internet hay muuuucha más documentación y textos para leer sobre esto (y en general, de cualquier cosa) en inglés. Entonces está bueno ir acostumbrándose a algunas definiciones en inglés por si quieren googlear algo.

La idea es arrancar yendo desde el nodo source al nodo más cercano. Supongamos que el nodo más cercano es el nodo A y está a distancia 4. Puede haber un camino más corto para, desde el source, llegar hasta A?

No, porque si lo hubiera, por ejemplo si el camino fuera S->B->A, significa que hay otro nodo (el B) que está a menos distancia de A, pero por definición sabemos que eso no pasa.

También vamos a guardar la información de “hasta este momento, la distancia más corta desde el source hasta el nodo X es D”. Entonces si hay una arista desde S hasta B de longitud 7, guardamos ese número.

Una vez que guardamos esa información para todos los vecinos de S, agarramos al nodo más cercano hasta S de los que todavía no vimos, en nuestro caso A.

Miramos los vecinos que no visitamos (o sea, a S no lo vamos a mirar), y nos fijamos si la distancia desde S hasta el nodo actual sumado a la longitud de la arista AV siendo V un vecino, es menor que la distancia que teníamos hasta el momento desde S hasta V. Si es más chico, actualizamos el valor como esa suma.

[DEMO ? GRAFIQUITOS ?]