ALGORITMO DE DIJKSTRA O SPF

A continuación vamos a explicar sobre el algoritmo de Dijkstra o también conocido como Shortest Path First con siglas SPF.

Este algoritmo nos sirve para lograr determinar cuál es el camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista, la idea principal de este algoritmo es de ir explorando todos los caminos más cortos que parten del vértice origen y llevan a cada uno de los vértices, una vez que se ha llegado a obtener el camino más corto a partir de nuestro vértice origen hasta nuestro destino el algoritmo se detiene. “El algoritmo de Dijkstra es un algoritmo de cálculo de ruta basado en estado del enlace. Para ilustrar como el algoritmo de Dijkstra  calcula la ruta optima, se va a suponer que el estado del enlace viene determinado por una métrica. De ser así, cada enlace debería tener asociado un valor numérico. Generalmente, este valor es inversamente proporcional a la capacidad del enlace y proporcional a la carga de este o una combinación ponderada de ambos. Por lo tanto, una ruta vendrá determinada por la suma de todas las métricas de todos los enlaces por los que se pase. Y la ruta optima, será aquella que menor métrica calculada tenga.” (Gil, 2010, 174). Podemos decir que este algoritmo tiene un tipo de búsqueda uniforme.

PASOS PARA EL ALGORITMO DE DIJKSTRA

Acá podemos observar cómo funciona el algoritmo teniendo en cuenta estos pasos.

Si bien parece algo un poquito difícil de entender podemos tomar en cuenta el siguiente video:

VENTAJAS

• Analiza cada métrica de coste para elegir la mejor ruta con el mínimo coste.
• Cada uno de los routers posee una información sobre la topología de la red.
• Admiten CIDR y VLSM.
• Para poder informar sobre cualquier cambio en la topología tiene como evento inundar la red mediante el protocolo LSA.

DESVENTAJAS

• Requiere un administrador de red el cual tenga conocimientos suficientes para administrar la misma.
• Debe tener un diseño jerárquico estricto para poder dividir la red en áreas más pequeñas, de modo que pueda reducir las tablas topológicas.
• Inunda la red mediante el protocolo VLSA la primera vez a modo de conocerla.

REFERENCIA BIBLIOGRÁFICA:

• Pablo Gil Vázquez, Jorge Pomares Baeza, Francisco Candelas Herias (2010). Redes y Transmision de datos. Ed: Universidad de Alicante.