Algoritmo de Dijkstra: Origen, Definición y Aplicaciones

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.



Las aplicaciones del algoritmo Dijkstra son muy diversas y de gran importancia en distintas áreas del conocimiento. Se presentan a continuación algunas de ellas.

• Encaminamiento de paquetes por los routers: se considera una red telefónica. En un momento dado, un mensaje puede tardar una cierta cantidad de tiempo en atravesar cada línea (debido a efectos de congestión, retrasos en las conexiones etc.). En este caso se tiene una red con costes en los arcos y dos nodos especiales: el nodo de comienzo y el de finalización, el objetivo aquí es encontrar un camino entre estos dos nodos cuyo coste total sea el mínimo.
• Aplicaciones para Sistemas de información geográficos: extracción de características curvilíneas de imágenes usando técnicas de minimización del camino: La imagen se representa como una matriz de puntos, cada uno con una especial intensidad. Cada nodo se corresponde con un punto (pixel) de la imagen y tiene hasta ocho nodos adyacentes. El peso de los arcos viene dado en este caso por la diferencia de intensidad. Esta técnica presenta un gran ahorro de costes frente a las herramientas existentes actualmente en el mercado que usan métodos de vectorización automáticos.
• Otras aplicaciones: enrutamiento de aviones y tráfico aéreo. Tratamiento de imágenes, médicas. Problemas de optimización de una función de coste para moverse entre diversas posiciones.

Aprender la teoría de grafos es importante, dado que con ella, se pueden resolver diversos problemas como por ejemplo: la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza en diferentes áreas del saber como lo son dibujo computacional, sistemas, administración, matemática, informática, electrónica, ciencias sociales y biología.

Los grafos son usados para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd. Los gps que utilizamos a diario desde nuestros smartphones o vehículos, realizan el cálculo de sus rutas basados en el algoritmo dijkstra, haciendo un estudio por medio de los grafos, para encontrar el camino mas corto a la ruta buscada. Actualmente, se están agregando nuevas variables, como lo son nivel de tráfico, estado de la calle a transitar, clima, entre otros, para que el sistema gps, facilite una óptima solución.

La teoría de grafos funciona dentro de las ciencias sociales, en especial para desarrollar un concepto no metafórico de red social que sustituye los nodos por los actores sociales y verifica la posición, centralidad e importancia de cada actor dentro de la red. Esta medida permite cuantificar y abstraer relaciones complejas, de manera que la estructura social puede representarse gráficamente. Por ejemplo, una red social puede representar la estructura de poder dentro de una sociedad al identificar los vínculos (aristas), su dirección e intensidad y da idea de la manera en que el poder se transmite y a quiénes.



Asimismo, se emplea en problemas de control de producción, para proyectar redes de ordenadores, para diseñar módulos electrónicos modernos y proyectar sistemas físicos con parámetros localizados (mecánicos, acústicos y eléctricos). Se emplean los grafos para la solución de problemas de genética y problemas de automatización de la proyección (SAPR). Apoyo matemático de los sistemas modernos para el procesamiento de la información.

Dentro de la programación android, se utiliza para resolver problemas asociados a los patrones de navegación comunes, a su vez, para el estudio de patrones de navegaciones basados en Fragmentos. El diagrama de una aplicación android está representado por un grafo dirigido, en el cual, podemos establecer las relaciones entre la actividad principal y todas las que se desarrollan a partir de ella. En el artículo "Guía de desarrolladores de Android para el Patrón de Navegación de Fragmentos" podemos observar como el autor Becze Szabolcs, hace uso de los grafos para representar las problemáticas asociadas a los patrones de navegación y cómo el desarrollo de las actividades por medio de fragmentos dan solución.

En otro orden de ideas, los grafos son utilizados dentro de el enrutamiento de un protocolo basado en vector de distancias, puesto que requiere que un router informe a sus vecinos de los cambios en la topología periódicamente y en algunos casos cuando se detecta un cambio en la topología de la red. Para finalizar, en la administración de proyectos, los grafos se utilizan en técnicas de revisión y evaluación de programas (PERT) en las que se modelan los mismos y son optimizandos los tiempos para concretarlos.