Algoritmo
de Dijkstra. También llamado
algoritmo de caminos mínimos, es un algoritmo 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.
Su nombre se refiere a Edsger
Dijkstra, quien lo describió por primera vez en 1959.
Aplicaciones
En
múltiples aplicaciones donde se aplican los grafos, es necesario conocer el
camino de menor costo entre dos vértices dados:
- Distribución de
productos a una red de establecimientos comerciales.
- Distribución de
correos postales.
- Sea G = (V, A)
un grafo dirigido ponderado.
El
problema del camino más corto de un vértice a otro consiste en
determinar el camino de menor costo, desde un vértice u a otro vértice v.
El costo de un camino es la suma de los costos (pesos) de los
arcos que lo conforman.
Características del algoritmo
- Es un
algoritmo greedy.
- Trabaja por
etapas, y toma en cada etapa la mejor solución sin considerar
consecuencias futuras.
- El óptimo encontrado
en una etapa puede modificarse posteriormente si surge una solución mejor.
Pasos para su aplicación
para
realizar la aplicación del algoritmo de Dijkstra, se aplican los siguientes
pasos:
1. Se
elige un nodo de inicio al cual se le marcara un peso de la siguiente Forma:
[X,Y]
(N).
Donde‘X’ equivale a el valor del recorrido actual de los
arcos,‘Y’ equivale a el nodo predecesor
o de origen y‘N’ al número de iteración u operación
actual.
2. A
los nodos adyacentes del nodo seleccionado como nodo de inicio, se deben asignar
un peso de igual forma al punto anterior, ([X,Y](N)).
3. De
los nodos con los pesos calculados se toma el nodo con menor calor en X y este
será el siguiente a visitar.
4. Los
pasos 2 y 3 deben repetirse teniendo en cuenta que si al intentar calcular los
pesos para los nodos adyacentes a un nodo que esta siendo visitado, uno de
estos ya tiene un peso asignado, deben calcularse los demás pesos cuantas veces
sean necesario, y siempre se tomara el peso mínimo calculado.
5. Los
nodos pueden ser visitados una sola vez
Ejemplo
de aplicación: Nodo de inicio A
Fuente:
0 comentarios:
Publicar un comentario