Ruta más corta
El problema de la ruta mas corta determina la distancia menor entre un punto de origen y un punto de destino.
Un problema de la ruta mas corta involucra una red conexa con un costo no negativo asociado a cada rama. A un nodo se le denomina fuente y a otro se le denomina destino. El objetivo es determinar una ruta que una a la fuente con el origen, de manera que la suma de los costos asociados con las ramas en la ruta sea la mínima.
DEFINICIÓN DEL PROBLEMA
- -Se tienen n nodos, partiendo del nodo inicial 1 y terminando en el nodo final n.
- -Arcos bidireccionales conectan los nodos i y j con distancias mayores que cero.
- -Se desea encontrar la ruta de mínima distancia que conecta el nodo 1 con el nodo n.
Por medio de la aplicación del algoritmo de este problema podemos conocer la menor distancia entre un nodo origen y un nodo destino.
Pasos a seguir:
- Elaborar un cuadro con todos los nodos y los ramales que salen de él.
- Partiendo del origen, debemos encontrar el nodo más cercano a él.
- Anular todos los ramales que entren al nodo más cercano elegido.
- Comenzando en el origen se debe encontrar el nodo más cercano a él, por intermedio del(los) nodo(s) ya elegido(s) y volver al tercer paso hasta llegar al destino.