Otras aplicaciones (I)

Antes de concluir con la presentación del problema de la ruta más corta, es necesario hacer hincapié en un punto. Hasta aquí, se ha descrito el problema en términos de minimizar la distancia de un origen a un destino. Sin embargo, en realidad el problema de redes que se estudia es el de encontrar cuál es la ruta que conecta a dos nodos específicos que minimiza la suma de los valores de las ligaduras sobre esa ruta. Por ejemplo, las ramas pueden corresponder a actividades de algún tipo y los valores asociados a cada una pueden representar el costo de esa actividad entonces, el problema sería encontrar qué secuencia de actividades logra el objetivo específico de minimizar el costo total relacionado. (Véase el problema 2.) Otra  posibilidad consiste en que el valor asociado a cada ligadura sea el tiempo requerido para realizar esa actividad. En este caso se desearía encontrar la secuencia de actividades que logra el objetivo específico de minimizar el tiempo total requerido. (véase el problema 6). Así, algunas de las aplicaciones más importantes del problema de la ruta más corta no tienen nada que ver con caminos en el sentido normal de la palabra.

Muchas aplicaciones requieren encontrar la trayectoria dirigida del origen al destino de una red dirigida. El algoritmo que acaba de presentarse se puede modificar con facilidad para que maneje trayectorias dirigidas en cada iteración. En particular, cuando se identifican candidatos para el n-ésimo nodo más cercano, sólo se considerarán los arcos dirigidos desde un nodo resuelto a un nodo no resuelto.