CAPÍTULO 4
4. ALGORITMO DE FLUJO DE COSTO MÍNIMO
4.1. Planteamiento del Problema de Flujo de Costo Mínimo
Sea G=(N,A) una red dirigida con un costo y una capacidad
asociada con cada arco A. El problema que se plantea es:
Minimizar
sujeto a
Se representará con C la mayor magnitud de los costos asociados
a los arcos y con U la mayor magnitud de la demanda u oferta de
algún arco o a la capacidad finita de dicho arco.
101
Se supondrá que el límite inferior de capacidad de cada arco ,
es cero. Además se harán las siguientes suposiciones:
1.-Todos los costos, ofertas, demandas y capacidades de los arcos
son enteros.
2.-La red es dirigida
3.-Las ofertas y las demandas de los nodos satisfacen la condición
y el problema de flujo de costo mínimo posee una
solución factible
4.- Supondremos que la red posee una ruta con una capacidad
ilimitada entre cada par de nodos de los arcos que la componen.
5.-Todos los costos de los arcos son no negativos.
Los algoritmos a ser analizados emplean el concepto de redes
residuales. En tales redes se ha reemplazado cada arco por
dos arcos y . El arco posee un costo y una
capacidad residual , y el arco tiene un costo
y una capacidad residual . La red residual está
compuesta de los arcos que posean una capacidad residual
positiva.
4.2. Algoritmo de Descomposición de Flujo
102
En la formulación de problemas de flujo en redes existen dos
formas de definir el flujo, la primera es definiendo el flujo sobre los
arcos y la segunda definiendo el flujo sobre rutas y ciclos.
Para analizar la definición de flujo sobre arcos, empleamos el
vector que satisface las siguientes restricciones:
donde,
Se observa que en este modelo hemos reemplazado la
oferta/demanda , por el término , al que denominaremos
como el desequilibrio del nodo i. Este término representa la
diferencia entre el flujo que llega al nodo i y el flujo que sale del
nodo. Por lo tanto si , se dice que i es un nodo de exceso.
Caso contrario, si diremos que i es un nodo de déficit. Si
afirmaremos que i es un nodo balanceado. La formulación
del problema sobre flujos en rutas y ciclos, comienza con la
enumeración de todas las rutas dirigidas P, entre algún par de
103
nodos y de todos los ciclos dirigidos en la red. Al conjunto de
todas las P, lo denotaremos con P y al conjunto de todos los ciclos
W con W. Las variables de decisión en esta formulación son el
flujo sobre la ruta P, f(P) y el flujo sobre el ciclo W f(W). Estas
variables están definidas para todos los elementos de P y W.
El flujo sobre el arco , es igual a la suma de los flujo f(P) y
f(w) de todos las rutas y ciclos que contienen al arco . De
manera formal definiremos a δij(P) igual a 1 si la ruta P contiene al
arco y 0 sino lo contiene, y a δij(W) igual a 1 si el ciclo W
contiene al arco y 0 sino lo contiene. Por lo tanto:
En relación a este razonamiento se establece el siguiente teorema:
4.2.1. Teorema de Descomposición de Flujo
Cada flujo en una ruta y en un ciclo tiene una única
representación como flujo no negativo sobre un arco.
Inversamente cada flujo no negativo puede ser representado
como un flujo sobre una ruta y un ciclo, aunque no
104
necesariamente de manera única, con las siguientes
propiedades:
a) Cada ruta dirigida con flujo positivo conecta un nodo de
déficit con un nodo de exceso.
b) Siendo n el número de nodos de una red y m el número
de arcos, a lo sumo n+m rutas y ciclos tiene un flujo no
nulo, de tal cantidad, a lo sumo m ciclos tienen flujo no
nulo.
4.2.1.1. Prueba
La demostración consistirá en una prueba algorítmica de cómo
descomponer un flujo sobre arcos en flujo sobre rutas y
ciclos. Para lo cual supongamos la existencia de un arco
que lleva una cantidad de flujo positiva desde un nodo de déficit
i0, hacia otro nodo i1. Nos detenemos si i1 es un nodo de
exceso, caso contrario existe otro arco con un flujo
positivo. Este proceso es repetido hasta que encontremos un
nodo de exceso ik, o hasta que visitemos el nodo de partida,
por lo que este paso se repetirá a lo sumo en n ocasiones. En
el primer caso habremos encontrado una ruta P, y en el
segundo un ciclo dirigido W.
105
En ambos casos, la ruta P y el ciclo W se componen de arcos
con flujo positivo. En la situación de que hayamos encontrado
una ruta P, definiremos al flujo f(P) de la siguiente manera:
y redefiniremos,
Si hubiésemos obtenido un ciclo dirigido W, definiremos al flujo
W de la siguiente forma:
y cambiando la variable:
Este proceso será repetido hasta que los desequilibrios de
cada nodo sean igual a cero. Luego se selecciona un nodo,
del que por lo menos emane un arco con flujo positivo, como el
106
nodo de partida y repetimos el proceso, el cual en este caso
debe encontrar un flujo positivo. Este proceso termina cuando
el flujo es igual a cero para el problema redefinido. Se
observa que el flujo original es la suma de los flujos
identificados sobre las rutas y ciclos por este método. En cada
ocasión en que se identifica una se reduce el exceso o el
déficit de un nodo a cero, y cada vez que se identifica el flujo
sobre una ruta dirigida se reduce el flujo sobre algún arco a
cero. Como consecuencia se tiene que la representación en
base a rutas y ciclos de un flujo positivo , contiene a lo sumo
m+n rutas y ciclos dirigidos, de los cuales a lo sumo m son
ciclos dirigidos.
Dada una circulación , para la cual para cada i N. Al
aplicar el algoritmo de descomposición de flujo a una
circulación , cada iteración descubre un ciclo dirigido
consistiendo solamente de arcos con flujo positivo y
subsecuentemente reduce el flujo de por lo menos un arco a
cero. Por lo que una circulación se descompone en flujos entre
a lo sumo m ciclos dirigidos. Debido a esto se enuncia la
siguiente propiedad.
107
4.2.2. Propiedad de la Circulación
Una circulación puede ser representada flujo sobre ciclos
en a lo sumo m ciclos dirigidos.
El teorema de descomposición de flujo nos permite
comparar dos soluciones de flujo en una red, nos permite
construir una solución a partir de otra mediante una
secuencia de operaciones simples. A continuación se
presenta la forma de cómo se establece un teorema
importante denominado Teorema del ciclo Aumentado.
Para ello se introduce el concepto de ciclo aumentado con
respecto a un flujo .
4.2.3. Ciclo Aumentado
Un ciclo W, no necesariamente dirigido, es llamado un
ciclo aumentado con respecto a un flujo , si aumentando
una cantidad positiva e flujo f(W) en torno al ciclo, el flujo
permanece factible. Tal operación incrementa el flujo de
los arcos dirigidos hacia delante, y decrementa el flujo de
los arcos dirigidos hacia atrás. Por lo tanto W es un ciclo
aumentado en G si para cada arco hacia
108
delante y para cada arco hacia atrás. Definiremos a
δij(W) igual a 1 si el arco es un arco hacia delante y
δij(W) será igual a –1 si el arco es un arco hacia atrás,
y 0 en otro caso.
El costo sobre el ciclo aumentado W viene definido como:
El cambio en el costo del flujo por aumentar f(W) unidades
de flujo es f(W)c(W). El teorema de descomposición de flujo
será empleado para enunciar otro teorema acerca de los
ciclos aumentados en términos de residuales. Para lo cual
supongamos que y son dos soluciones factibles del
problema de flujo de costo mínimo.
De acuerdo a las redes residuales se tiene que para alguna
circulación factible en G(xl) satisface la propiedad de que
. Además es posible representar a la circulación x l
como flujos sobre ciclos con
. Además se tiene que:
109
Por lo que se ha establecido el siguiente resultado:
4.2.4. Teorema del Ciclo Aumentado
Suponga que y que son dos soluciones factibles de un
problema de flujo en una red. Entonces equivale a más
el flujo sobre a lo sumo m ciclos dirigidos en G(x0). Además,
el costo de equivale el costo de más el costo de flujo
sobre esos ciclos aumentados.
4.3. Condiciones de Optimización
Dado un nodo fuente s y para cada nodo j N, definamos a
, con j s, como la longitud de la ruta más corta desde el
nodo s al nodo j. Por lo que para cada arco se debe
satisfacer la siguiente desigualdad:
110
Esta condición nos provee de un medio para verificar si una
ruta es la de menor longitud desde un nodo fuente s hacia
otros nodos. A continuación presentamos dos condiciones de
optimización equivalentes para el problema de flujo de costo
mínimo.
4.3.1. Condiciones de Optimización de Ciclo Negativo
Esta condición proviene de las propiedades del teorema de
descomposición de flujo en redes y de la redes residuales.
La condición de optimización de ciclo negativo viene dada
por el siguiente teorema:
4.3.1.1. Teorema de Condiciones de Optimización de Ciclo
Negativo
Una solución factible es una solución óptima del
problema de flujo de costo mínimo, sí solo sí satisface las
condiciones de optimización de ciclo negativo, es decir la
red residual G(x*) contiene ciclos dirigidos con costos no
negativos.
111
4.3.1.1.1. Prueba.
Asumamos que es un flujo factible y que G(x) contiene
un ciclo negativo. Si sucede esto no puede ser una
solución óptima, debido a que si aumentamos una
cantidad positiva de flujo en el ciclo, lo que logramos es
mejorar el valor de la función objetivo. Debido a esto si
es una solución óptima se debe cumplir que G(x*)
no contenga ciclos negativos.
Ahora supongamos que es un flujo factible y que
G(x*) contiene ciclos no negativos. Además definamos a
como un flujo óptimo. De acuerdo a la propiedad de
ciclo aumentado es posible descomponer el vector
diferencia en a lo sumo m ciclos aumentados
con respecto al flujo , la suma de costos de esos
ciclos es igual , como la longitud de todos los
ciclos en G(x*) son no negativos se tiene que esta
diferencia de costos es mayor o igual a cero o en forma
equivalente se tendría:
112
Debido a que es un flujo óptimo se cumple que,
Por lo que se concluye que y es también
una solución óptima. Finalmente este argumento
muestra que si G(x*) contiene ciclos no negativos
entonces debe ser una solución óptima.
4.3.2. Condición de Optimización de Costo Reducido
La condición de optimización antes descrita se la puede
escribir de la siguiente manera:
para todos los arcos A
es un costo reducido óptimo para el arco en el
sentido que mide los costos del arco relativo a las distancias
y . Se observa que los costos reducidos de cada
arco son no negativos.
El costo reducido es igual a cero si el arco forma parte
de la ruta de menor longitud desde el nodo s al nodo j. Por
113
lo que si se conocen las distancias más cortas , la ruta
de mínimo costo estará conformada por los arcos con costo
reducido igual a cero. Pero falta verificar si esta condición
es aplicable a los problemas más generales de flujo de
costo mínimo.
Supongamos que se asocia un número real , sin
restricción de signo, con cada nodo i N. A dicho nodo lo
denominaremos el potencial del nodo i. Se definirá al costo
reducido del arco como:
Este costo es aplicable a las redes residuales y a red
original. Los costos en las redes residuales se definirán
empleando en lugar de . A continuación se presentan
dos propiedades importantes de los costos reducidos.
4.3.2.1. Propiedad
a) Para alguna ruta dirigida P, desde el nodo k al nodo l,
se tiene que:
114
b) Para algún ciclo dirigido W,
En base a estas propiedades es posible obtener una forma
alternativa de la condición de optimización de ciclo
negativo.
Una solución factible es una solución óptima del
problema de flujo de costo mínimo sí solo sí algún conjunto
de nodos potenciales satisface las siguientes
condiciones de optimización de costo reducido:
para cada arco en G(x*)
4.3.2.1.1. Prueba
Supongamos que una solución satisface las
condiciones mencionadas. Por lo tanto para
cada ciclo dirigido W en G(x*). Debido a las propiedades
anteriores se cumple que:
115
de esta forma se comprueba que G(x*) contiene ciclos no
negativos.
Para demostrar lo inverso, supondremos que para la
solución , G(x*) contiene ciclos no negativos.
Supongamos que las distancias de las rutas más
cortas, desde el nodo l hacia los demás nodos en G(x*).
Hay que tomar en cuenta que si la red contiene ciclos no
negativos, las distancias están bien definidas y
satisfacen las condiciones para cada arco
en G(X*) . Estas desigualdades se pueden escribir
como o , si es que se
define . Por lo que la solución satisface las
condiciones de optimización de costo reducido.
Las condiciones de optimización de costo reducido
tienen una interesante interpretación económica.
Supongamos que se interpreta a como el costo de
transportar una unidad de un artículo desde el nodo i al
nodo j a través del arco . A se lo
116
interpretará como el costo de obtener una unidad del
artículo en el nodo i.
De acuerdo a esto se tiene que es el costo del
artículo en el nodo j, si se lo obtiene en el nodo i y se lo
transporta al nodo j. La condición de optimización de
costo reducido, o de forma equivalente
, establece que el costo de obtener el
artículo en el nodo j, no es mayor que si obtuviéramos el
artículo en el nodo i y lo transportáramos del nodo i al
nodo j. El costo en el nodo j podría ser más pequeño
que debido a que es posible que exista otra
forma de transportar un artículo del nodo i al nodo j a
través de otros nodos.
4.3.3. Condiciones de Optimización Complementarias
A continuación se presenta una condición de optimización
en términos de la red original.
4.3.3.1. Teorema de Condiciones de Optimización
Complementarias
117
Una solución factible x* es una óptima solución del
problema de flujo de costo mínimo sí solo sí para un
conjunto de nodos potenciales , los costos reducidos y
los valores de los flujos satisfacen las siguientes
condiciones de optimización para cada arco A:
1.- Si , entonces
2.- Si , entonces
3.- Si ,
4.3.3.1.1. Prueba
En la prueba se demostrará que las condiciones
anteriores son equivalentes a las condiciones de
optimización de costo reducido.
Para establecer este resultado probaremos que si los
potenciales de los nodos y el vector de flujo
satisfacen las condiciones de optimización de costo
reducido entonces ellos deben satisfacer las condiciones
expresadas en este teorema. Para esto consideraremos
las tres posibilidades para algún arco A.
118
Caso 1. Si , la red residual no puede contener al
arco (j,i), porque para ese arco, lo que
contradice las condiciones de optimización de costo
reducido. Por lo tanto .
Caso 2. Si , la red residual contiene a ambos
arcos y . Las condiciones de optimización de
costo reducido implican que y . Pero debido
a que , esas desigualdades implican que
.
Caso 3. Si , la red residual no puede contener al
arco porque para ese arco, lo que contradice
a las condiciones de optimización de costo reducido. Por
lo tanto .
De esta manera se concluye la demostración del
teorema.
4.4. Dualidad del Problema de Flujo de Costo Mínimo
119
Los problemas de programación lineal son denominados
problemas primales y a cada uno es posible asociar otro problema
relacionado o dual. Por ejemplo el máximo valor de la función
objetivo del problema dual equivale al mínimo valor de la función
objetivo para el problema primal. A continuación se establecerán
los resultados de la dualidad correspondientes al problema de flujo
de costo mínimo.
Al formular el problema dual de un problema primal es necesario
asociar una variable dual con cada restricción del problema primal,
excepto con las restricciones de no negatividad de flujo en los
arcos. Con cada restricción de balance de masa del problema de
flujo de costo mínimo se asocia la variable dual y la variable
con cada restricción de capacidad de los arcos . Por lo que el
problema dual de flujo de costo mínimo queda establecido de la
siguiente forma.
Sujeto a:
para cada arco
120
para cada arco y es irrestricto en signo
para
A continuación se presentan dos teoremas acerca de la teoría de
dualidad en el problema de flujo de costo mínimo.
4.4.1. Teorema de Dualidad Débil
Sea el valor de la función objetivo para alguna solución factible
del problema de flujo de costo mínimo y sea el valor de la
función objetivo para alguna solución factible de su problema dual.
Entonces .
4.4.1.1. Prueba
Si se multiplica a ambos miembros de la siguiente desigualdad.
Por y se suman para cada arco se obtiene la
expresión:
121
Se tiene que , debido a que
. Además . Por lo tanto
la desigualdad queda de la siguiente manera
Se observa que el lado izquierdo de la desigualdad es la función
objetivo dual y el lado derecho es la función objetivo primal, por
lo que se ha demostrado el teorema. A partir del resultado
anterior, se puede concluir que si para alguna solución dual
y para una solución primal las funciones objetivo
tienen el mismo valor, entonces son soluciones óptimas del
problema dual y del problema primal respectivamente. La
interrogante que se plantea es la existencia de tales soluciones,
para responderla en primer lugar se deben eliminar las variables
duales . De acuerdo a la definición de costo reducido es
posible escribir la desigualdad , de la
siguiente manera:
122
En la función objetivo dual el coeficiente asociado a la variable
dual es y nuestro propósito es maximizar el valor de la
función objetivo, por lo que la variable dual debería tener el
valor más pequeño posible, entonces:
Si se conocen los valores de las variables es posible
calcular los valores de las variables . Según lo anterior la
función objetivo dual queda de la siguiente manera:
Maximizar
El problema dual consiste en encontrar el vector que optimice
esta función. El siguiente teorema demostrará la existencia de
las soluciones óptimas mencionadas.
4.4.2. Teorema de Dualidad Fuerte
El problema de flujo de costo mínimo siempre tiene una solución
y el problema de flujo de costo mínimo dual tiene una solución que
satisface la propiedad que
123
4.4.2.1. Prueba
En esta prueba se emplean las condiciones de optimización
complementarias. Sea una solución óptima del problema de
flujo de costo mínimo. Según tales condiciones, esta solución junto
con un vector satisfacen las condiciones de optimización
complementarias. Como consecuencia se tiene que la solución
satisface la siguiente condición:
Consideremos los siguientes casos:
1)
2)
3)
Según las condiciones de optimización complementarias, en los dos
primeros casos los miembros de la condición anterior son iguales a
cero y en el tercer caso ambos son iguales a
Sustituyendo la expresión en la función
objetivo dual:
124
Se obtiene como resultado:
Por lo que se demuestra el teorema.
4.5. Algoritmo de la Ruta Sucesiva más Corta
Este algoritmo en cada paso selecciona un nodo s con exceso
de oferta, es decir, una cantidad de oferta que todavía no es
enviada a un nodo de demanda, y un nodo t con demanda
insatisfecha y envía flujo desde el nodo s al nodo t a través de
la ruta con la distancia más corta. El algoritmo termina cuado
la solución actual satisface todas las restricciones.
Para describir el algoritmo, introduciremos el concepto de
pseudoflujos. Un pseudoflujo es una función que
satisface solo las restricciones de capacidad y no negatividad.
No necesita satisfacer las restricciones de balance de masa.
Para algún pseudoflujo , definimos el desequilibrio del nodo i
como sigue:
125
para cada i
Si para algún nodo i, nos referimos a como el
exceso del nodo i; si denominamos a como el
déficit del nodo i. Uno nodo está balanceado si . Sean
E y D los conjuntos de los nodos con excesos y déficit de flujo
en la red respectivamente.
Se observa que:
y
Por lo tanto si la red contiene un nodo de exceso, también
debe contener un nodo de déficit. La red residual
correspondiente a un pseudoflujo es definida de la misma
manera que para un flujo.
A continuación se presenta un lema, el cual se plantea
utilizando las condiciones de optimización de costo reducido.
126
4.5.1. Lema
Suponga que un pseudoflujo (o un flujo) satisface las
condiciones de optimización de costo reducido con respecto
a algunos potenciales de los nodos . Supongamos que el
vector representa las rutas más cortas desde el nodo s a
todos los otros nodos en la red residual G(x) con como la
longitud de una arco . Entonces las siguientes
propiedades son válidas:
a) El pseudoflujo también satisface las condiciones de
optimización de costo reducido con respecto a los
potenciales de los nodos .
b) Los costos reducidos son cero para todos los arcos
en las rutas más cortas desde el nodo s a cada uno de los
otros nodos.
4.5.1.1. Prueba
Ya que el flujo satisface las condiciones de optimización
de costo reducido con respecto a , para cada arco
127
en G(x). Además ya que el vector representa las
distancias de las rutas más cortas con como longitudes
de los arcos, satisface las condiciones de optimización de
la ruta más corta, es decir:
para todos los arcos en G(x)
Substituyendo en la expresión anterior,
obtenemos:
Alternativamente, , o
. Esta conclusión establece la parte a) del lema.
Consideremos la ruta más corta desde el nodo s hasta
algún nodo i. Para cada arco , en esta ruta
. Substituyendo en esta
ecuación obtenemos . Esta conclusión establece la
parte b) del lema.
4.5.2. Lema
128
Suponga que un pseudoflujo (o un flujo) satisface las
condiciones de optimización de costo reducido y obtenemos
a partir de , enviando flujo a lo largo de la ruta más corta
desde el nodo s a algún nodo k; entonces también
satisface las condiciones de optimización de costo reducido.
4.5.2.1. Prueba
Definamos los potenciales y como en el lema
anterior. La demostración de tal lema implica que para
cada arco en la ruta más corta P desde el nodo s
hasta el nodo k.
Aumentando flujo a través de algún arco, añadiría el arco
inverso a la red residual. Pero ya que para cada
arco , y el arco también satisface las
condiciones de optimización de costo reducido.
Los potenciales de los nodos juegan un papel muy
importante en este algoritmo, el cual se describe a
continuación:
129
4.5.3. Descripción del Algoritmo Ruta Sucesiva más Corta
Comienzo
=0 y
para todo
inicializar los conjuntos y
Mientras hacer
Comienzo
Seleccione un nodo y un nodo ;
Determine las distancias de las rutas más cortas
desde el nodo K a todos los otros nodos en G(x)
con respecto a los costos reducidos ;
Defina a P como la ruta más corta desde del nodo k
al nodo l;
Actualice
;
incrementar unidades de flujo a lo largo de la ruta
P;
Actualizar x, G(x), E, D y los costos reducidos;
Fin;
Fin;
130
A continuación justificaremos el algoritmo de flujo de costo
mínimo. Para iniciar el algoritmo, asignamos =0, el cual
es un pseudoflujo factible. Para un pseudoflujo de cero se
tiene que G(x)=G. Se observa que esta solución junto con
satisfaces las condiciones de optimización de costo
reducido porque para arco
en la red residual G(x), lo que concuerda con los
supuestos del problema de flujo de costo mínimo. Se
observa que con tal de que algún nodo tenga un
desequilibrio diferente de cero, ambos conjuntos E y D
deben ser no vacíos desde que la suma total de los
excesos es igual a la suma total de los déficit. De esta
manera, hasta que todos los nodos estén balanceados, el
algoritmo continua siempre identificando un nodo de
exceso k y un nodo de déficit l.
Uno de los supuestos del problema, indica que la red
residual contiene una ruta dirigida desde el nodo k a cada
uno de los otros nodos, incluyendo el nodo l. Por lo tanto
las distancias de las rutas más cortas , están bien
definidas. Cada iteración del algoritmo resuelve un
problema de la ruta más corta con longitudes de los arcos
131
no negativos y estrictamente decrementa el exceso de
algún nodo y también el déficit de algún otro nodo.
Consecuentemente si U es el límite superior sobre la
oferta más grande de algún nodo, el algoritmo terminaría
en a lo mucho iteraciones.
Este algoritmo selecciona un nodo de exceso k y utiliza el
algoritmo de Dijkstra para identificar las rutas más cortas
desde el nodo k hacia los demás nodos y aumenta el flujo
a través de la ruta más corta desde el nodo k, hasta el
nodo l. No es necesario determinar la ruta más corta
desde el nodo k hasta todos los demás nodos, es
suficiente la ruta más corta desde el nodo k hasta un nodo
de déficit l. Por lo tanto el algoritmo de Dijkstra terminaría
si queda etiquetado permanentemente el nodo de déficit l.
En este punto podemos modificar los potenciales de los
nodos de la siguiente manera:
Si el nodo i es etiquetado permanentemente
Si el nodo i es etiquetado temporalmente
132
4.5.4. Algoritmo de Dijkstra
Este algoritmo encuentra las rutas más cortas desde un nodo
fuente s, hasta todos los demás nodos en la red, con costos
asociados a sus arcos no negativos. El algoritmo mantiene
una distancia con cada nodo i, la cual es un límite
superior sobre la longitud de la ruta más corta al nodo i. En
algún paso intermedio el algoritmo divide al conjunto de
nodos en dos grupos: el primero denominado etiquetados
permanentemente o permanentes y el segundo grupo
denominados etiquetados temporalmente o temporales.
La etiqueta de distancia para algún nodo permanente
representa la distancia más corta desde el nodo fuente a tal
nodo. Para algún nodo temporal la etiqueta de distancia es
el límite superior de la distancia más corta a ese nodo.
La idea del algoritmo es abrirse paso desde el nodo s y
permanentemente etiquetar nodos en el orden de sus
distancias desde el nodo s. Inicialmente se le asigna a s una
etiqueta permanente de cero y a cada uno de los demás
nodos se les asigna una etiqueta igual a infinito.
133
En cada iteración, la etiqueta de un nodo i es su distancia
más corta desde el nodo fuente a lo largo de una ruta cuyos
nodos interiores están todos, permanentemente etiquetados.
El algoritmo selecciona un nodo i con la mínima etiqueta
temporal, la hace permanente y se extiende desde ese nodo,
es decir analiza los arcos en A(i) para actualizar las etiquetas
de distancia de los nodos adyacentes. El algoritmo finaliza
cuando todos los nodos han sido etiquetados como
permanentes. El algoritmo construye un árbol con raíz desde
el nodo fuente que abarca los nodos etiquetados con
distancias finitas. El algoritmo mantiene los nodos
empleando índices o punteros. Es decir si Árbol
entonces pred(j)=i. Además se mantiene la propiedad de que
para cada arco del árbol se tiene que .
En el algoritmo de Dijkstra nos referimos a la operación de
seleccionar la mínima distancia temporal como operación de
selección del nodo. A la operación de verificar si las
etiquetas de los nodos satisfacen la condición de que
, si es así se realiza la asignación
, la que se conoce como la operación de
134
actualización de distancia. A continuación se presentan los
pasos que conforman el algoritmo de Dijkstra.
4.5.4.1. Descripción del Algoritmo de Dijkstra
Comienzo
;
para cada nodo ;
y ;
Mientras cardinalidad(S)<n hacer
Comienzo
Sea un nodo para el cual
;
;
Para cada hacer
Si entonces
y pred(j)=i
Fin;
Fin;
En ciertos problemas de flujo no es necesario determinar la
ruta más corta desde un nodo fuente s hasta cada uno de
135
los demás nodos en la red, sino hasta un nodo específico t.
Por lo que se presentan las siguientes variantes del
algoritmo de Dijkstra.
4.5.4.2. Algoritmo de Dijkstra hacia Atrás
En el algoritmo de Dijkstra se determina la ruta más corta
E desde un nodo s a cada uno de los nodos en .
Suponga que se desea determinar la ruta más corta desde
cada uno de los nodos en hasta el nodo de llegada t.
Para resolver este problema se emplea una modificación
del algoritmo de Dijkstra. El algoritmo de Dijkstra hacia
atrás mantiene una distancia con cada nodo j, el cual
es el límite superior de la longitud de la ruta más corta
desde el nodo j hasta el nodo t. De forma análoga este
algoritmo designa un conjunto de nodos llamado
permanentemente etiquetado y el conjunto restante de
nodos llamado temporalmente etiquetado .
En cada iteración el algoritmo designa con la etiqueta con
la mínima distancia temporal, denominada , como
permanente. Se examina cada arco de llegada y
modifica la etiqueta de la distancia del nodo i a
136
. El algoritmo termina cuando todos
los nodos se han convertido en etiquetados
permanentemente.
4.5.4.3. Algoritmo de Dijkstra Bidireccional
Este algoritmo se emplea para determinar la ruta más corta
desde un nodo fuente s hasta un nodo de llegada t. Para
resolver este problema y eliminar algunos cálculos se
podría dar por finalizado el algoritmo de Dijkstra tan pronto
como se haya seleccionado un nodo t .
En el algoritmo bidireccional de Dijkstra simultáneamente
se aplica el algoritmo de Dijkstra convencional, desde el
nodo s y el algoritmo de Dijkstra hacia atrás desde el nodo
t. Alternativamente designa un nodo en y un nodo en
como permanente hasta que ambos algoritmos hayan
etiquetado permanentemente el mismo nodo, llamado el
nodo k por lo que se tendría que .
Supongamos que P(i) denota la ruta más corta desde el
nodo s al nodo encontrada por el algoritmo de Dijkstra
tradicional y sea P’(j) la ruta más corta desde el nodo s al
137
nodo al nodo t encontrado por el algoritmo de
Dijkstra. al nodo t encontrado por el algoritmo de Dijkstra.
138
Top Related