Aplicaciones del Algoritmo Dijkstra

por Violeta León

    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. 





Anuncio

Comentarios

  1. Pero... sigo sin entender que el algoritmo Dijkstra :(

    ResponderEliminar
    Respuestas
    1. Nena debes acceder a http://ingenieradeideas.blogspot.com/2014/04/algoritmo-de-dijkstra-origen-y.html allí explicó el origen y definición del algoritmo.

      Eliminar

Publicar un comentario