Las aplicaciones del algoritmo de Dijkstra son muy diversas y de gran importancia en distintas áreas del conocimiento:
- Encaminamiento de paquetes por los routers:
Consideremos 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 tenemos 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. - Caminos mínimos en Grafos usando XML y parsers de Java:
El concepto de camino es una secuencia de operadores y conectores: un operador será cualquier unidad de proceso de información realizando un algoritmo específico (i.e. conversores digitales, de Formato etc.) Y un conector será cualquier mecanismo a través del cual los operadores se comunican entre sí. Dado un conjunto de descripciones de operadores y conectores, unos parámetros de optimización (que el usuario queda encargado de introducir) y una serie de requisitos, el sistema se encargará de encontrar un camino óptimo de una entrada establecida hasta un tipo de salida especificada aplicando transformaciones específicas en el menor tiempo posible.
Suscribirse a:
Entradas
(Atom)
0 comentarios:
Publicar un comentario