Algoritmo de Dijkstra

11 – Matem´aticas I : Teor´ıa de Grafos

1.3

1.3 Caminos de peso m´ınimo. Algoritmo de Dijkstra

Caminos de peso m´ınimo. Algoritmo de Dijkstra

Cuando un grafo modela una situaci´
on, en general, las conexiones (aristas y arcos) tienen adem´as unas
caracter´ısticas propias. Pensemos en el ejemplo de una red viaria o una red el´ectrica, no s´olo se trata de
dar el servicio (conexi´
on), sino quetambi´en es interesante conocer las longitudes de las l´ıneas a establecer
(cantidad de material), las dificultades para su trazado (coste en tiempo o monetario), etc.
En el grafo, estos valores se reflejan asignando a cada arista un valor que represente la magnitud que
queremos considerar (un peso a cada arista).
Consideremos el grafo de la derecha, donde a cada arista le hemos asignado unadistancia.
Si buscamos ahora el camino “m´as corto” entre el v´ertice v1
v2
v4
v6
7
2
s
s
s
y v3 no consideraremos que es el que tiene menos aristas,
 ❅
 ❅
 
 
 
 
sino aquel que recorre en total menor distancia: C1 = v1 v3
❅8
❅1
3
 
 
v
3
5
s
 
4
1
❅
❅
recorre s´olo una arista pero una distancia de 9, C2 = v1 v2 v3
 ❅
 ❅
❅
7
tiene dos aristas y una distancia total de 6 y C3 = v1 v2 v5 v3
 9
❅
❅
9❅❅ 
❅s
❅ 
s 
s
tiene tres aristas sin embargo la distancia recorrida es s´olo
v3
1
v5
v7
de 5. Claramente, este u
´ltimo camino es m´as corto.
Definici´
on 19.- Llamaremos peso de un grafo (o digrafo) G = (V, A) a una funci´on real positiva sobre
el conjunto de aristas del grafo, es decir, a una funci´on ω: A → IR+ .
El peso de cada arista lo denotaremos por ω({vi , vj }) = ωij y llamaremos peso deuna trayectoria
a la suma de los pesos de las aristas que la componen.
En un grafo pesado, se llama matriz de pesos del grafo a la matriz Ω = (ωij )n×n , donde pondremos
ωij = ∞ si no hay arista desde el v´ertice vi al v´ertice vj y ωii = 0, ceros en la diagonal. (En ocasiones
puede resultar u
´til poner tambi´en en la diagonal el valor ∞ y, de hecho, algunos autores as´ı lo hacen.)
Nota: Con laintroducci´
on del peso, la b´
usqueda del camino m´as corto y la “matriz de alcance” vistas en
la secci´on anterior son un caso particular: cuando el peso de cada arista es 1.
Unifiquemos criterios y notaci´
on:
Definici´
on 20.- Llamaremos peso m´ınimo de vi a vj al m´ınimo de los pesos de los caminos de vi a vj ,
∗ , y camino (de peso) m´
lo denotaremos por ωij
ınimo de vi a vj a cualquier caminoCij entre ellos que
∗ ).
tenga peso m´ınimo (es decir, ω(Cij ) = ωij
∗)
∗
La matriz de pesos m´ınimos es la matriz Ω∗ = (ωij
n×n con ωij = ∞ si no hay camino de vi a vj .
El siguiente resultado, conocido como el Principio de minimalidad de Bellman, y que b´asicamente
dice “cualquier camino contenido en un camino m´ınimo es tambi´en m´ınimo”, garantiza que los caminos
obtenidos –respetando esteprincipio– son caminos m´ınimos.
Proposici´
on 21.- Sea G un grafo pesado. Si x1 x2 · · · xp−1 xp es un camino m´ınimo, para cada i con
∗ = w∗ + w∗ .
1 < i < p, los caminos x1 x2 · · · xi y xi · · · xp−1 xp son caminos m´ınimos y w1p
1i
ip
Demostraci´on:
Es claro el resultado, pues si el camino C1i = x1 x2 · · · xi−1 xi no es un camino m´ınimo, existe otro
C1i = x1 x2 · · · xi−1 xi , con w(C1i ) de sustituir C1i por C1i , tiene menor peso que x1 x2 · · · xi−1 xi · · · xp , en contra de la hip´otesis.

1.3.1

Algoritmo de Dijkstra

Uno de los algoritmos m´as usados para la b´
usqueda de caminos de peso m´ınimo es el de Dijkstra, que
proporciona los pesos m´ınimos desde un v´ertice dado al resto de los v´ertices.
Estealgoritmo aplica el principio de Bellman de manera constructiva (casi al rev´es que lo que dice
la tesis de Bellman) formando un camino m´ınimo a partir de otro ya existente. El algoritmo devuelve
en realidad el peso m´ınimo no el camino m´ınimo propiamente dicho, pero permite obtener f´acilmente el
camino m´ınimo recorriendo en sentido inverso la construcci´on (de ah´ı su popularidad).
Prof:...

Leer documento completo

Regístrate para leer el documento completo.