Si los pesos de mis aristas son de valor 1, entonces bastará con usar el algoritmo de BFS.
Si los pesos de mis aristas son negativos no puedo usar el algoritmo de dijsktra, para pesos negativos tenemos otro algoritmo llamado Algoritmo de Bellmand-Ford.}
Primero marcamos todos los vértices como no utilizados. El algoritmo parte de un vértice origen que será ingresado, a partir de ese vértices evaluaremos sus adyacentes, como dijkstra usa una técnica greedy – La técnica greedy utiliza el principio de que para que un camino sea óptimo, todos los caminos que contiene también deben ser óptimos- entre todos los vértices adyacentes, buscamos el que esté más cerca de nuestro punto origen,
lo tomamos como punto intermedio y vemos si podemos llegar más rápido a través de este vértice a los demás. Después escogemos al siguiente más cercano (con las distancias ya actualizadas) y repetimos el proceso. Esto lo hacemos hasta que el vértice no utilizado más cercano sea nuestro destino. Al proceso de actualizar las distancias tomando como punto intermedio al nuevo vértice se le conoce como relajación (relaxation).
EJ
teniendo el siguiente grafo, se desarrolla el algoritmo Dijkstra.
Se tiene una etiqueta para cada nodo de la siguiente forma:
[D,O]i
Donde:
D=es la distancia acumulada
O=el origen o procedencia
i=numero de iteración
Para nodo inicial, la etiqueta es:
Se calcula las etiquetas para los tres nodos adyacentes para esta primera iteración
Se toma el nodo donde la etiqueta indica la menor distancia, para este caso es 5
Se calcula las etiquetas de los nodos faltantes partiendo del nuevo nodo marcado
En los casos donde los nodos tienen dos etiquetas, del cálculo anterior y el actual, se deja aquel de menor distancia
El nuevo nodo es aquel que tiene la etiqueta de menor distancia, que es 2 y se calcula las nuevas etiquetas con respecto a este
Evaluando las 2 etiquetas del nodo se mantiene la anterior, y se marca el nodo
En el último nodo, se mantiene su etiqueta por ser de menor distancia con respecto al nodo 5
Se calcula las etiquetas para los tres nodos adyacentes para esta primera iteración
Se calcula las etiquetas de los nodos faltantes partiendo del nuevo nodo marcado
En los casos donde los nodos tienen dos etiquetas, del cálculo anterior y el actual, se deja aquel de menor distancia
El nuevo nodo es aquel que tiene la etiqueta de menor distancia, que es 2 y se calcula las nuevas etiquetas con respecto a este
Evaluando las 2 etiquetas del nodo se mantiene la anterior, y se marca el nodo
En el último nodo, se mantiene su etiqueta por ser de menor distancia con respecto al nodo 5
Con este grafo y sus etiquetas, se entiende las distancias y recorridos del nodo inicial (1), para cualquier nodo en el camino de menor costo.
video
No hay comentarios:
Publicar un comentario