La Ruta Mas Corta

ALGORITMO DE LA RUTA MÁS CORTA


Un problema de la ruta más corta involucra una red conexa con un costo no negativo asociado a cada rama. A un nodo se le denomina fuente y a otro nodo se ledenomina 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 mínima.
Los problemas de la ruta másbarata se resuelven mediante el siguiente algoritmo, en cuya aplicación todo empate será resuelto arbitrariamente.

Paso 1.

Constrúyase una lista maestra tabulando bajo cada nodo, en ordenascendente según el costo, las ramas que llegan a él. Cada rama bajo un nodo dado, se escribe con ese nodo como su primer nodo. Omítase en la lista cualquier rama que tenga a la fuente como susegundo nodo o que tenga al destino como su primer nodo.



Paso 2.

Márquese con un asterisco a la fuente y asígnese el valor 0. Localícese la rama más barata que coincida con la fuente yenciérrese en un círculo. Márquese con un asterisco al segundo nodo de esta rama y asígnese a este nodo un valor igual al costo de la rama. Elimínense de la lista maestra todas aquellas otrasramas que tengan como segundo nodo al que se acaba de marcar con asterisco

Paso 3

Si el nodo que acaba de marcarse con asterisco es el destino continúese en el paso 5. Si no, continúeseen el paso 4.

Paso 4.

Considérense en la lista maestro actual, todos los nodos marcados con asterisco que tengan bajo ellos ramas muy cerradas en un círculo. Para cada uno de ellos,agréguese el valor asignado al nodo, al costo de la rama sin círculo mas barata bajo él. Denótese a la menor de estas sumas con M y enciérrese en un círculo la rama cuyo costo contribuyó a M. Márquese conun asterisco el segundo nodo de esta rama y asígnesele el valor M. Elimínense de la lista maestra todas las otras ramas que tengan al nodo que acaba de marcarse con asterisco como segundo nodo....