La ruta mas corta

Un problema de la ruta más corta involucra una gráfica conexa con un peso no negativo asociado a cada rama. A un nodo se le denomina fuente y a otro nodo se le denomina destino. El objetivo es determinar una ruta que una a la fuente con el destino, tal que la suma de los pesos asociados con las ramas en la ruta sea mínima.

Este tipo de problemas se resuelve aplicando el siguiente algoritmo, en cuya aplicación todo empate será resuelto arbitrariamente.

Paso 1. Construya una lista maestra tabulando bajo cada nodo, en orden ascendente según el peso, las ramas que llegan a él. Cada rama bajo un nodo dado, se escribe con ese nodo como su primer nodo. Omita en la lista cualquier rama que tenga a la fuente como su segundo nodo o que tenga al destino como su primer nodo.

Paso 2. Marque con un asterisco a la fuente y asígnele el valor cero. Localice la rama más barata que coincida con la fuente y enciérrela “en un círculo”. Marque con asterisco al segundo nodo de esta rama y asígnele a este nodo un valor igual al peso de la rama. Elimine de la lista maestra todas aquellas otras ramas que tengan como segundo nodo al que acaba de marcar con asterisco.

Paso 3. Si el nodo que acaba de marcar con asterisco es el destino, continúe en el paso 5. Si no, continúe en el paso 4.

Paso 4. Considérense en la lista maestra actual, todos los nodos marcados con asterisco que tengan bajo ellos ramas marcadas “muy cerradas en círculo”. Para cada uno de ellos, agréguese el valor asignado al nodo, al peso de la rama “sin círculo” no marcada más barato bajo él. Denótese a la menor de estas sumas con M y encierre en un círculo la rama cuyo peso contribuyó a M. marque con un asterisco el segundo nodo de esta rama y asígnele el valor M. elimine de la lista maestra todas las otras ramas que tengan al nodo que acaba de marcar con asterisco como segundo nodo. Continúe en el paso 3.

Paso 5. es el valor asignado al destino. Una ruta de costo mínimo se obtiene recursivamente, iniciando con el destino, al incluir en la ruta cada rama encerrada en círculo cuyo segundo nodo pertenece a la ruta.

Una persona que vive en R, y que trabaja en W, busca una ruta que minimice el tiempo matutino de transporte. Esta persona ha registrado los tiempos (en minutos) de transporte en las vías principales que comunican a las diferentes ciudades intermedias; estos datos se dan en la tabla. La anotación punteada indica que ninguna autopista importante une directamente a los puntos correspondientes. Determinar la mejor ruta para esta persona de ir desde R hasta W.

R C O T P W

R … 18 … 32 … …

C 18 12 28

O … 12 … 17 … 32

T 32 28 17 … 4 17

...