Algoritmo De Dijkstra

Algoritmo de Dijkstra

Es la creación de la mínima distancia desde un nodo origen y los nodos “destinos”, este algoritmo analiza todas las interacciones y posibles rutas que puede realizar pormedio de los caminos. Seleccionando la mejor solución posible y más factible también es conocido como el camino más cortó y la descripción de este algoritmo fue realizada por el holandés Edsger WybeDijkstra indicando el inicio de este algoritmo en 1959.
El algoritmo de dijkstra es un algoritmo que tiene la siguiente representación


Lo cual indica que “n” es el número de vértices buscando elcosto mínimo desde el nodo origen a los demás nodos del grafico el fundamento de este algoritmo es el principio de optimalidad
Este algoritmo tiene una estructura llamada cola de prioridad lo queindica que se genera un orden según la importancia asociada a cada recorrido la manera de iniciar este algoritmo es encontrar el nodo no visitado con la menor distancia de recorrido “indicando queeste será el nodo de inicio”.
Procedimiento
1. Indicar el nodo origen
2. Sumamos las distancias en los distintos nodos con la distancia de los nodos que podemos acceder seleccionando la menordistancia
3. Seleccionando el nodo actual donde nos encontramos como recorrido o visitado y volvemos al paso 1.





Aplicaciones de algoritmo de dijkstra
Encaminamiento de paquetes por routers : elejemplo es de un recorrido en una llamada de red telefónica indicando el tiempo de recorrido en atravesar las líneas teniendo en cuenta congestión o retrasos de conexiones.
Aplicación para sistema deinformación geográficos: indica el mínimo recorrido seleccionando características curvilíneas durante todo el recorrido buscando aprovechar un mayor recorrido en un menor costo
Enrutamiento deaviones y tráfico aéreo: coordinación de rutas y planes de vuelo desde un punto específico hasta su destino.
Importancias del algoritmo
1. Si los pesos de las aristas son de valor uno podemos usar...