PROBLEMA DEL CAMINO MAS CORTO
Es una red en el cual cada arco (i,j) tiene asociado un numero (Cij) el cual representa la distancia desde el nodo" i "hasta el nodo "j " , o tal vez el costo o el tiempo el objetivo principal es encontrar la ruta desde un nodo especifico hasta cada uno de los demás nodos de la red.
- ALGORITMO DE LA RUTA MAS CORTA (DIJKSTRA)
- Marca todos los nodos a los que se puede llegar desde el nodo inicial con etiquetas temporales , la etiqueta que se pondrá sera ( distancia inicial , nombre del nodo inicial ).
- Evaluar todos los nodos con etiquetas temporales , cual posee la distancia mas corta en la etiqueta. Marcalo con etiqueta permanente utilizando un (*).
- Etiquetar todos los nodos a los que se puede llegar desde el ultimo nodo con etiqueta permanente, si ya tienen una etiqueta temporal , esta se revalúa con respecto a la distancia del nodo permanente con que se esta trabajando. Si la distancia que da es menos que la que tiene en etiqueta esta es cambiada por una nueva etiqueta con la distancia calculada a la etiqueta permanente.
- Se examina todas las etiquetas temporales existentes, la que tenga la distancia mas pequeña se marca como etiqueta permanente y se repite el paso 3 hasta que todas las etiquetas sean permanente.
Ejemplo:
- Marca todos los nodos a los que se puede llegar desde el nodo inicial con etiquetas temporales , la etiqueta que se pondrá sera ( distancia inicial , nombre del nodo inicial ).
- Evaluar todos los nodos con etiquetas temporales , cual posee la distancia mas corta en la etiqueta. Marcalo con etiqueta permanente utilizando un (*).
- Etiquetar todos los nodos a los que se puede llegar desde el ultimo nodo con etiqueta permanente, si ya tienen una etiqueta temporal , esta se revalúa con respecto a la distancia del nodo permanente con que se esta trabajando. Si la distancia que da es menos que la que tiene en etiqueta esta es cambiada por una nueva etiqueta con la distancia calculada a la etiqueta permanente.
- Se examina todas las etiquetas temporales existentes, la que tenga la distancia mas pequeña se marca como etiqueta permanente y se repite el paso 3 hasta que todas las etiquetas sean permanente.
No hay comentarios:
Publicar un comentario