Algoritmo de Dijkstra

Algoritmo de Dijkstra

Uno de los algoritmos mas usados para la búsqueda de caminos de peso mínimo es
el de Dijkstra, que proporciona los pesos mínimos desde un vértice dado al resto de
los vértices.

Ejemplo en codigo:

El vector D final contiene los pesos mınimos desde el vertice inicial a los demas
vertices –si alguno de los pesos finales es ∞, no hay camino desde el vertice inicial–.

El vector D final contiene los pesos mınimos desde el vertice inicial a los demas
vertices –si alguno de los pesos finales es ∞, no hay camino desde el vertice inicial–.

Para la aplicacion del algoritmo con lapiz y papel, se coloca el vector D inicial como
la primera fila de una tabla, de manera que en las filas sucesivas se van colocando
los nuevos valores de D tras cada minoracion.

Cita

“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)

texto citado de http://electropediadelsaber.blogspot.com/2012/10/algoritmo-de-dijkstra-o-spf.html