La red de la figura 6.
15 da las rutas permisibles y sus longitudes en millas entre la ciudad 1 (nodo
1) y las otras cuatro ciudades (nodos 2 a 5). Determine las rutas más cortas entre la ciudad 1 y
cada una de las cuatro ciudades restantes.
Iteración 0. Asigne una etiqueta permanente [0, -] al nodo 1.
Iteración 1. Se puede llegar a los nodos 2 y 3 desde el nodo 1 (el último etiquetado
perma- nentemente). Así, la lista de nodos etiquetados (temporales y
permanentes) es
Nodo Etiqueta Estado
1 [0, —] Permanente
2 [0 + 100, 1] = [100, 1] Temporal
3 [0 + 30, 1] = [30, 1] Temporal
Para las dos etiquetas temporales [100,1] y [30,1], el nodo 3 da la distancia
míni- ma (u3 = 30). De este modo, el estado del nodo 3 cambia a permanente.
Iteración 2. Se puede llegar a los nodos 4 y 5 desde el nodo 3, y la lista de los nodos etique-
tados es
Nodo Etiqueta Estado
1 [0, —] Permanente
2 [100, 1] Temporal
3 [30, 1] Permanente
4 [30 + 10, 3] = [40, 3] Temporal
5 [30 + 60, 3] = [90, 3] Temporal
La etiqueta temporal [40,3] en el nodo 4 ahora es permanente (u4 = 40).
2
15
4
100 20
10 50
30 60
1 3 5
FIGURA 6.15
Ejemplo de red para el algoritmo de la ruta más corta de Dijkstra
Iteración 3. Desde el nodo 4 se puede llegar a los nodos 2 y 5 Así, la lista de los nodos
eti- quetados se actualiza como
Nodo Etiqueta Estado
1 [0, —] Permanente
2 [40 + 15, 4] = [55, 4] Temporal
3 [30, 1] Permanente
4 [40, 3] Permanente
5 [90, 3] o
[40 + 50, 4] = [90, 4] Temporal
En el nodo 2, la nueva etiqueta [55,4] reemplaza a la etiqueta temporal
[100,1] de la iteración 1 porque proporciona una ruta más corta. Además, en
la itera- ción 3 el nodo 5 tiene dos etiquetas alternativas con la misma
distancia (u5 = 90). La etiqueta temporal [55,4] en el nodo 2 ahora es
permanente (u2 = 55).
Iteración 4. Sólo el nodo 3 permanentemente etiquetado puede ser alcanzado desde el nodo
2. Por consiguiente el nodo 3 no puede ser reetiquetado. La nueva lista de eti-
quetas permanece como estaba en la iteración 3 excepto que la etiqueta en el
nodo 2 ahora es permanente. Esto deja al nodo 5 como la única etiqueta
tempo- ral. Como el nodo 5 no conduce a otros nodos, su etiqueta se hace
permanente, y el proceso termina.
Los cálculos del algoritmo pueden realizarse directamente en la red, como lo demuestra
la figura 6.16.
La ruta más corta entre el nodo 1 y cualquier otro nodo en la red se determina partiendo
del nodo destino deseado y retrocediendo hasta el nodo de inicio utilizando la información en
las etiquetas permanentes. Por ejemplo, la siguiente secuencia determina la ruta más corta del
nodo 1 al nodo 2:
(2) → [55, 4] → (4) → [40, 3] → (3) → [30, 1] → (1)
Por lo tanto, la ruta deseada es 1 → 3 → 4 → 2 con una distancia total de 55 millas.
FIGURA 6.16
Procedimiento de etiquetado en el algoritmo de Dijkstra
[100,1](1)
[55,4](3)
2
15
[40,3](2)
4
100 20
10 50
30 60 [90,3](2)
[0,—](1) 1 3 5 [90,4](3)
[30,1](1)
( ) = iteración
