5

PROBLEMA DE LA RUTA
MÁS CORTA

Introducción
En el siguiente tema aprenderemos a encontrar la
ruta mas corta en un problema de redes, es decir,
aplicar el algoritmo de la ruta mas corta para
encontrar la menor distancia de un punto origen a un
destino, de entre una serie de nodos conectados
entre si para llegar a un mismo destino. Este tipo de
problema se utiliza en problemas de logística yplaneación de rutas, para minimizar los cotos, tiempo
de llegada y especialmente para planear las rutas de
entrega.

Ejemplo (REMPLAZO
DE EQUIPO)
• RentCar esta desarrollando una política de reemplazo
para su flotilla de automóviles en el horizonte de
planeación de 4 años. Al inicio de cada año, un
automóvil se reemplaza o se conserva en operación
durante un años mas. Un automóvil debe estar enservicio de 1 a 3 años. La siguiente tabla proporciona
el costo de reemplazo como una función del año en
que se adquiere el automóvil y los años en operación.

Costo de reemplazo ($) para años dados en operación
Equipo adquirido
al inicio del año

1

2

3

1

4000

5400

9800

2

4300

6200

8700

3

4800

7100

----

4

4900

-----

----

• El problema puede formularse como una red en la que
losnodos 1 a 5 representan el inicio de los años 1 a 5.
los arcos a partir del nodo 1 (años 1) pueden llegar a
los nodos 2,3 y 4 por que un automóvil puede estar en
operación de 1 a 3 años. Los arcos a partir de los
demás nodos pueden interpretarse del mismo modo.
La longitud de cada arco es igual al costo del
remplazo. La solución del problema es equivalente a
determinar la ruta mas corta entre losnodos 1 y 5.

• La ruta mas corta es 1-3-5
• La solución indica que un automóvil adquirido al inicio
del año 1 (nodo 1) debe remplazarse después de 2
años al inicio del año 3 (nodo2). El automóvil de
reemplazo entonces en servicio hasta finales del años
4. el costo total de reemplazo es de $12,500
(=$5400+$7100)

1

2

3

4

5

Algoritmos de la ruta
más corta
1. Algoritmo de Dijkstra para determinarlas rutas más cortas
entre el nodo origen y los demás nodos en la red.
2. Algoritmo de Floyd para determinar la ruta mas corta entre
dos nodos cualesquiera en la red.

a
r
t
s
k
j
i
D
e
d
o
m
t
i
r
o
g
Al

• El algoritmo de Dijkstra, también llamado algoritmo de
caminos
mínimos,
es
un algoritmo para
la
determinación del camino más corto.
•  Su nombre se refiere a Edsger Dijkstra, quien lodescribió por primera vez en 1959.
• La idea subyacente en este algoritmo consiste en ir
explorando todos los caminos más cortos que parten
del vértice origen y que llevan a todos los demás
vértices; cuando se obtiene el camino más corto desde
el vértice origen, al resto de vértices que componen el
grafo, el algoritmo se detiene.

•

Sea la distancia más corta del nodo origen
1 al nodo i, y definida (≥ 0) como la
longitud del arco ( i, j ). El algoritmo define
la etiqueta para un nodo j que sigue
•   inmediatamente como:

• La etiqueta para el nodo de inicio es [0,2],
que indica el nodo no tiene predecesor.
• Las etiquetas de nodo en algoritmo de
Dijkstra son de dos tipos: temporales y
permanentes.
• Una etiqueta temporal en un nodo modifica si
puede hallarse una ruta más corta al nodo.
Delo contrario, el estado temporal cambia a
permanente.

• Paso 0: etiquete el nodo de origen (nodo 1)
con la etiqueta permanente [0,-], establezca i
=1
• Paso general i:
•a)  Calcule las etiquetas temporales para cada
nodo j con ≥ 0, siempre que j no este
etiquetado permanentemente. Si el nodo j
ya tiene una etiqueta temporal existente
hasta otro nodo k y si < , reemplace con .

b) Si todos losnodos tienen etiquetas
permanentes deténgase. De lo contrario,
seleccione la etiqueta
que tenga la
•   distancia más corta ( =) entre todas las
etiquetas temporales (rompa los empates
arbitrariamente).

Ejemplo
• La red de la siguiente figura de las rutas
permisibles y sus longitudes en millas entre la
ciudad 1(nodo 1) y las otras 4 ciudades (nodos 2 a
5). Determine las rutas mas cortas entre la...