Algoritmo de Dijkstra

Es un algoritmo para poder encontrar el camino mas corto desde un vértice al resto. Su utilidad se puede aplicar en un grafo donde las aristas este en una distancia de la conexión entre dos lugares y sea necesario averiguar el camino mas corto para llegar a un punto. Se puede decir que se puede determinar la secuencia de aristas para llegar a un nodo partir de un coste mínimo. El algoritmo genera uno a uno los caminos de un nodo al resto. En otras palabras, cada router calcula el algoritmo SPF y determina el costo desde su propia perspectiva.

Podemos ver un ejemplo:
El costo de la ruta más corta para que R2 envíe paquetes a la LAN conectada a R3 es 27. Aquí se observa que este costo no es 27 para que todos los routers alcancen la LAN conectada a R3. Cada router determina su propio costo hacia cada destino en la topología.

Referencias Bibliográficas

Protocoles de enrutamiento (2012). Algoritmo SPF. Obtenido de http://protocolosdeenrutamiento.wikispaces.com/Algoritmo+SPF el 8 de octubre de 2012.

Arxiv(2012). Acerca del algoritmo de Dijkstra. Obtenido de http://arxiv.org/pdf/0810.0075.pdf el 8 de octubre de 2012