Antología de Investigación de Operaciones
Ingeniería en Sistemas Computacionales
2.4. Problema de la ruta más corta.
Aunque existen muchas versiones de problemas de la ruta más corta, la atención se centrará en la versión sencilla. Considere una red conexa y no dirigida con 2 nodos especialmente llamados origen y destino. A cada ligadura( arco no dirigido) se asocia una distancia no negativa. El objetivo es encontrar la ruta más corta del origen al destino.
Se dispone de un algoritmo relativamente sencillo para manejar este problema. La esencia del procedimiento es que analiza toda la red a partir del origen; identifica de manera sucesiva la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias( más cortas), desde el origen; el problema queda resuelto en el momento de llegar al nodo destino. Primero se describirá el método y después se ejemplificará con la solución del problema de la ruta más corta que enfrenta la administración de Seervada Park en la siguiente sección.
Algoritmo de la Ruta más Corta
Objetivo de la n-ésima iteración: Encontrar el n-ésimo nodo más cercano al origen( Este paso se repetirá para n = 1, 2, … hasta que el n-ésimo nodo más cercano sea el nodo destino).
Datos de la n-ésima iteración: n – 1 nodos más cercanos al origen – que se encontró enlas iteraciones previas-, incluida su ruta más corta y la distancia desde el origen.( Estos nodos y el origen se llaman nodos resueltos; el resto son nodos no resueltos).
Candidatos para n-ésimo nodo más cercano: cada nodo resuelto que tiene conexión directa por una ligadura con uno o más nodos no resueltos proporcionan un candidato – esto es, el nodo no resuelto que tiene la ligadura más corta-.( Los empates proporcionan candidatos adicionales).
Cálculo del n-ésimo nodo más cercano: para cada nodo resuelto y sus candidatos, se suma la distancia entre ellos y la distancia de la ruta más corta desde el origen a este nodo resuelto. El candidato con la distancia total más pequeña es el n-ésimo nodo más cercano – los empates proporcionan nodos resueltos adicionales-, y su ruta más corta es la que genera esta distancia.
Aplicación del algoritmo al problema de Seervada Park
La administración de Seervada Park necesita encontrar la ruta más corta desde la entrada del parque( nodo O) hasta el mirador( nodo T) a través del sistema de caminos que se presenta en la siguiente figura. En la tabla se encuentran los resultados obtenidos al aplicar el algoritmo anterior – donde el empate del segundo nodo más cercano permite pasar directo a buscar el cuarto nodo más cercano-. La primera columna( n) indica el número de la iteración, después de quitar los que no sirven – los que no tienen conexión directa con nodos no resueltos-. La tercera columna da los candidatos para el n-ésimo nodo más cercano – nodos no resueltos con la ligadura más corta al nodo resuelto-. La cuarta columna calcula la distancia de la ruta más corta desde el origen a cada candidato – esto es, la distancia al nodo resuelto más la de la ligadura que va al candidato-. El candidato con la suma de distancias más pequeñas es el n-ésimo nodo más cercano al origen, según se indica en la quinta columna. Las dos últimas columnas resumen la información de este último nodo resuelto necesitaría para pasar a las iteraciones siguientes – es decir, la distancia de la ruta más corta del origen a este nodo y la última rama en esta ruta-.
43