 |
| 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.