Problema de la ruta más corta

Aunque al final de la sección se mencionan otras versiones del problema de la ruta más corta (incluyendo algunas para redes dirigidas), la atención se centrará en la siguiente versión sencilla. Considérese una red conexa y no dirigida con dos nodos especiales llamados origen y destinos. A cada una de las ligaduras (arcos no dirigidos) se asocia una distancia no negativa. El objetivo es encontrar la ruta más corta (la trayectoria con la mínima distancia total) que va del origen al destino.

Se dispone de un algoritmo relativamente sencillo para este problema. La esencia de este procedimiento es que analiza toda la red a partir del origen, identificando sucesivamente la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias (más cortas), desde el origen, quedando resuelto el problema en el momento de llegar al nodo destino. Primero se describirá el método y después se ejempleficara con la solución del problema de la rauta más corta que enfrenta la administración de Seervada Park en la sección 10.1