SuperNotes by yuri.rodrix

Notas de YuriRod

Página tipo blog en el que voy a publicar mis notas de aprendizaje, en especial de temas como matemáticas, física y quizá algo de programación

Redes neuronales
Redes neuronales
Redes neuronales
Redes neuronales
Redes neuronales
Redes neuronales

Link-State (LS) — Dijkstra

Playground interactivo del algoritmo de Dijkstra. Crea nodos haciendo click en el lienzo, conéctalos con pesos enteros positivos, elige un origen y avanza paso a paso. En cada iteración el algoritmo revisa los vecinos del nodo actual (resaltado en ámbar), escoge el de menor costo tentativo (rojo) y lo cierra (verde), repitiendo el proceso desde ese nuevo nodo.

peso por defecto:anim ms:
origen: — · fase: idle
4215810263ABCDEF
origen actual / arista en revisión arista mínima escogida cerrado / árbol alcanzable
Bitácora

Sin pasos aún.

Modo: Crear / mover nodo

Click en el lienzo para crear un nodo. Arrastra un nodo existente para moverlo.

Tabla de iteraciones
PasoNL(A), p(A)L(B), p(B)L(C), p(C)L(D), p(D)L(E), p(E)L(F), p(F)

Una celda queda vacía cuando ese nodo entró a N en o antes de ese paso (su distancia ya está definitiva).

Árbol invertido

Aún no hay nodos cerrados.

Cada arista del árbol viene de prev[v] y se etiqueta con el peso original. El árbol crece a medida que se cierran nodos.

Tabla de distancias

Selecciona un origen y pulsa Iniciar.

Idea del algoritmo

  1. Inicializa d(v)=∞ para todo nodo, y d(s)=0 para el origen.
  2. Marca el origen como “actual”. Para cada vecino no visitado, calcula la distancia tentativa d(u)+w(u,v) y relaja si mejora la mejor conocida.
  3. De entre los nodos no visitados, escoge el de menor distancia tentativa: ese pasa a ser el nuevo “actual” (y se considera cerrado).
  4. Repite hasta que no queden nodos alcanzables sin visitar.

La condición clave —y la razón por la que Dijkstra exige pesos no negativos— es que al escoger siempre el mínimo entre los no visitados se garantiza que su distancia ya no puede mejorar por otra ruta.