5 Ruta Mas Corta En Grafos

5

RUTA MÁS CORTA EN GRAFOS

Una importante aplicación de las técnicas de programación dinámica es la determinación de rutas
de costo mínimo, en grafos. Este problema, así como otros relacionados, conforman una clase de
problemas con muchas situaciones reales en las que el estudio teórico puede aplicarse. Para definir
los términos del problema:
Sea G(V,E,c) un grafo dirigido etiquetado, i.e.,

Ves un conjunto de vértices o nodos,

E  VxV es un conjunto de arcos,

c: E  R* es una función que etiqueta los arcos 1, i.e., para eE, c(e) es la etiqueta de e.
Es usual que el grafo G(V,E,c) sea finito, es decir, que el conjunto de vértices V lo sea. Como
convención para las discusiones siguientes, se supondrá que V = {1,2,,n}. La etiqueta de un
arco representa una especie de costo de latransición entre los vértices que se conectan.
Un camino de longitud m, desde el vértice u0 hasta el vértice um es una secuencia
r = u0,u1, ,um  V+

tal que, para i=0,,m-1, (ui,ui+1)E. En este caso, se define el costo del camino r como:
costo(r) := +: 0i
El grafo G(V,E,c) se puede representar con una matriz de distancias (directas) D =(dij) 
Mn(R*), definida de modo que,para 1i,jn:
d(i,i) := 0,
d(i,j) := c(i,j)
d(i,j) := 

, si (i,j)E,
, si (i,j)E

La representación es tal que se olvida el costo de las "buclas" o "lazos", i.e., si hay un arco con
c(i,i)>0, la representación lo "cambia" por otro de costo 0. La razón para esta decisión es el
interés en determinar costos mínimos de caminos entre vértices; de esta forma, un camino que
1 R* := R+  {0,}utilice un lazo de costo positivo siempre tiene costo mayor que otro que no lo usa. Por otro lado, los
vértices originalmente no conectados, se consideran ligados por un arco de costo infinito.
Ya en el Ejemplo 4 de 3.5.1 se mostró que, a partir de multiplicaciones de matrices Mn(R*) se
puede determinar la matriz D* =(d*ij), donde d*ij es, precisamente, el costo de un camino de costo
mínimo del vérticei al vértice j. Entonces, D* se llama la matriz de distancias mínimas.
Con esta notación, se plantean los siguientes problemas:

Encontrar D*.

Dado un vértice u, encontrar d*u., i.e., d*uv, para vV.

Dados dos vértices u,v, encontrar d*uv.
Es claro que cualquier solución del problema de encontrar la matriz de distancias mínimas resuelve
los otros dos problemas y que, resolver el problema decostos mínimos de un vértice a todos los
demás conlleva una solución para encontrar el costo mínimo entre dos vértices. Por el contrario, es
fácil construir soluciones de los problemas más complejos a partir de soluciones para los simples.
En cada problema planteado, resulta interesante, además de conocer el costo mínimo
correspondiente, conocer la forma en que se consigue, es decir, determinarcaminos de costo
mínimo.

5.1

RUTA MÁS CORTA ENTRE CADA PAR DE VÉRTICES

Se quiere solucionar el problema de calcular D*, es decir, determinar, para 1i,jn, el valor de
*

dij



min: r es un camino de i a j: costo(r)

Una especificación del problema para una solución algorítmica:
Ctx: m: array[1..n,1..n] of R*
Pre: m = D
Pos: m = D*

La búsqueda de una solución puede afrontarse con técnicas deprogramación dinámica. En primer
lugar, conviene definir el siguiente léxico:
Para WV, i,jV:
W

Rij
W
Cij

:= {r | r = camino, para k=1,,m: wkW}
W

:=

De esta manera, para 1i,jn:

*
V
dij = Cij.

Entonces se puede establecer una recurrencia para calcular los CWij , WV, i,jV:
C
ij

=

Dij

5 Ruta más corta en grafos

2

CW{v}
ij

=

W

W

Wmin{Cij, Civ + Cvj} , para vW

En particular, si ahora se denota C1..k
como Ckij, se tiene que:
ij
k

Cij

=

Dij

=

k-1
min{Cij ,

, si k=0
k-1
Cik

+

k-1
Ckj }

, si 0
Esta recurrencia es la base fundamental para establecer la corrección del llamado algoritmo de
Floyd-Warshall:
proc FW (var m:array[1..n,1..n] of R*)
{Pre:

m = D}

{Pos:

m = D*}



k:= 0;
{Inv P: 0kn  m = Ck }
do kn...

Leer documento completo

Regístrate para leer el documento completo.