Casos especiales - El Problema de la ruta mas corta

Ahora se considerará la versión del problema de la ruta más corta presentada en la sección 10.3 (encontrará la ruta más corta desde un origen a un destino a través de una red no dirigida). Para formular este problema como un problema del flujo de costo mínimo se establece el origen como un nodo de recursos con una cantidad de 1, el destino como un nodo de demanda con una demanda de 1 y el restode los nodos son nodos de trasbordo. DEbido a que la red para el problema de la ruta m;as corta es no dirigida, mientras que se supone que el problema del flujo de costo mínimo tiene una red dirigida, cada ligadura se sustituye por un par de arcos dirigidos en direcciones opuestas (dibujados como una sola línea con cabezas de flechas en ambas terminales). Las únicas expceciones son que no hay necesidad de preocuparse por aros que llegan al nodo origen ni que salen de nodo destino. La distancia entre los nodos i y j se convierten en unidades de costo cij o cji para el flujo, en cualquier dirección entre estos nodos. Igual que con los casos especiales anteriores no se imponen capacidades a los arcos por lo que todo uij = ∞.

La figura 10.13 muestra que esta formulación para el problema de la ruta más corta, para Seervada Park que se presentó en la figura 10.1, en donde los números cerca de las líneas ahora representan el costo unitario del flujo en cualquier dirección.