Algoritmo de Dijkstra: Origen y Definición

por Violeta León

Origen del Algoritmo de Dijkstra
     
     Edsger Wybe Dijkstra nació en Rotterdam, (Holanda) en 1930. Sus padres eran ambos intelectuales y él recibió una excelente educación. En 1942, cuando Dijkstra tenía 12 años, entró en Gymnasium Erasminium, una escuela para estudiantes especialmente brillantes. Se especializó en el ámbito de la informática generando grandes aportes como lo son la notación polaca inversa, el algoritmo shunting yard; fue uno de los principales diseñadores del lenguaje de programación ALGOL. Fue en 1956, Dijkstra anunció su algoritmo, algoritmo de caminos mínimos, y desde entonces es utilizado bajo su apellido, “el algoritmo de dijkstra”.

Definición de Grafos
         
        Un grafo es un conjunto de puntos (vértices) en el espacio, que están conectados por un conjunto de líneas (aristas). En notación matemática se describe así: un Grafo G es un par ordenado G=(V,E) donde, V es un conjunto de vértices o nodos y E es un conjunto de aristas o arcos que relacionan los vértices entre sí. Normalmente, V es una cantidad finita para poder ejercer operaciones con los datos obtenidos del Grafo.

         Una de las propiedades de los grafos es la ponderación, la cuál es la herramienta útil para el desarrollo del algoritmo dijkstra que se explicará más adelante. Consiste en asociar a cada arista un valor, el que representa costo, peso, longitud; dependiendo de la función que cumpla el Grafo. Es a menudo utilizado para problemas de optimización. El peso de cada arista se denota por ω({vi; vj}) = ωij y se define como peso de una trayectoria a la suma de los pesos de las aristas que la componen.

         En un grafo pesado, se llama matriz de pesos del grafo a la matriz  Ω= (ωij)nxn, donde se coloca ωij = ∞  si no hay arista desde el vértice vi al vértice vj y ωii = o, ceros en la diagonal.

Algoritmo Dijkstra

         El algoritmo Dijkstra o también llamado algoritmo de caminos mínimos,  es un algoritmo eficiente para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Éste se encarga de formar un camino a partir de otro ya existente.


         El algoritmo Dijkstra trabaja por etapas bajo el principio de la optimalidad,  tomando en cada etapa la mejor solución sin considerar consecuencias futuras; donde el óptimo encontrado puede modificarse posteriormente si surge una solución mejor. El algoritmo devuelve en realidad el peso mínimo, no el camino mínimo propiamente dicho.







Anuncio

Comentarios