Algoritmo de Dijkstra

Todos los protocolos de routing de estado de enlace aplican el algoritmo de Dijkstra para calcular la mejor ruta. A este algoritmo se le llama comúnmente “algoritmo SPF” (Primero la ruta más corta). Para determinar el costo total de una ruta, este algoritmo utiliza costos acumulados a lo largo de cada ruta, de origen a destino.

En la figura, cada ruta se rotula con un valor arbitrario para el costo. El costo de la ruta más corta para que el R2 envíe paquetes a la LAN conectada al R3 es 27. Cada router determina su propio costo hacia cada destino en la topología. En otros términos, cada router calcula el algoritmo SPF y determina el costo desde su propia perspectiva.

Nota: el objetivo central de esta sección es analizar el costo, el cual está determinado por el árbol SPF. Por este motivo, en los gráficos de esta sección se muestran las conexiones del árbol SPF y no la topología. Todos los enlaces se representan mediante una línea negra continua.