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.
