Grafos

Algortimos para determinar Caminos M´ ınimos en Grafos

Algoritmos y Estructuras de Datos III

Camino m´ ınimo en grafos
Sea G = (V , X ) un grafo y l : X → R una funci´n de o longitud/peso para las aristas de G . Definiciones: La longitud de un camino C entre dos nodos v y u es la suma de las longitudes de las aristas del camino: l(C ) =
e∈C

l(e)

Un camino m´ ınimo C 0 entre u y v esun camino entre u y v tal que l(C 0 ) = m´ ın{l(C )|C es un camino entre u y v }. Puede haber varios caminos m´ ınimos.

Camino m´ ınimo en grafos
Dado un grafo G , se pueden definir tres variantes de problemas sobre caminos m´ ınimos: ´ Unico origen - unico destino: Determinar un camino m´ ´ ınimo entre dos v´rtices espec´ e ıficos, v y u. ´ Unico origen - m´ltiples destinos: Determinar uncamino m´ u ınimo desde un v´rtice espec´ e ıfico v al resto de los v´rtices e de G . M´ltiples or´ u ıgenes - m´ltiples destinos: Determinar un camino u m´ ınimo entre todo par de v´rtices de G . e Todos estos conceptos se pueden adaptar cuando se trabaja con un grafo orientado.

Camino m´ ınimo en grafos
Aristas con peso negativo: Si el grafo G no contiene ciclos de peso negativo o contienealguno pero no es alcanzable desde v , entonces el problema sigue estando bien definido, aunque algunos caminos puedan tener longitud negativa. Sin embargo, si G tiene alg´n ciclo con peso negativo alcanzable u desde v , el concepto de camino de peso m´ ınimo deja de estar bien definido. Circuitos: Un camino m´ ınimo no puede contener circuitos. Propiedad de subestructura ´ptima de un camino o m´ ınimo:Dado un digrafo G = (V , X ) con una funci´n de o peso l : X → R, sea P : v1 . . . vk un camino m´ ınimo de v1 a vk . Entonces ∀1 ≤ i ≤ j ≤ k, Pvi vj es un camino m´ ınimo desde vi a vj .

´ Camino m´ ınimo en grafos - Unico origen-m´ltiples destinos u
Problema: Dado G = (V , X ) un grafo y l : X → R una funci´n o que asigna a cada arco una cierta longitud y v ∈ V un nodo del grafo, calcularlos caminos m´ ınimos de v al resto de los nodos. Distintas situaciones: El grafo puede ser orientado o no. Todos los arcos tienen longitud no negativa. No hay un circuito orientado de longitud negativa. Hay circuitos orientados de longitud negativa. Queremos calcular los caminos m´ ınimos entre todos los pares de nodos.

Algoritmo de Dijkstra (1959)
Asumimos que las longitudes de las aristasson positivas. El grafo puede ser orientado o no orientado.
S := {v }, π(v ) := 0 para todo u ∈ V hacer si (v , u) ∈ X entonces π(u) := l(v , u) si no π(u) := ∞ fin si fin para mientras S = V hacer elegir w ∈ V \ S tal que π(w ) = m´ u∈V \S π(u) ın S := S ∪ w para todo u ∈ V \ S y (w , u) ∈ X hacer si π(u) > π(w ) + l(w , u) entonces π(u) := π(w ) + l(w , u) fin si fin para fin mientras retornar πAlgoritmo de Dijkstra (1959) - Determina camino m´ ınimo
S := {v }, π(v ) := 0, pred(v ) := 0 para todo u ∈ V hacer si (v , u) ∈ X entonces π(u) := l(v , u), pred(u) := v si no π(w ) := ∞, pred(w ) := ∞ fin si fin para mientras S = V hacer elegir w ∈ V \ S tal que π(w ) = m´ u∈V \S π(u) ın S := S ∪ w para todo u ∈ V \ S y (w , u) ∈ X hacer si π(u) > π(w ) + l(w , u) entonces π(u) := π(w ) + l(w ,u) pred(u) := w fin si fin para fin mientras retornar π, pred

Algoritmo de Dijkstra - Ejemplo

2 4 1 3 6 7

3

3 1

1

1 4

4

3

5

Algoritmo de Dijkstra - Ejemplo
S = {1} π = (0, ?, ?, ?, ?, ?)

2 4 1 3 6 7

3

3 1

1

1 4

4

3

5

Algoritmo de Dijkstra - Ejemplo
S = {1} π = (0, 4, 7, ∞, ∞, 3)

2 4 1 3 6 7

3

3 1

1

1 4

4

3

5Algoritmo de Dijkstra - Ejemplo
S = {1, 6} π = (0, 4, 7, ∞, ∞, 3)

2 4 1 3 6 7

3

3 1

1

1 4

4

3

5

Algoritmo de Dijkstra - Ejemplo
S = {1, 6} π = (0, 4, 7, ∞, ∞, 3)

2 4 1 3 6 7

3

3 1

1

1 4

4

3

5

Algoritmo de Dijkstra - Ejemplo
S = {1, 6} π = (0, 4, 7, ∞, 6, 3)

2 4 1 3 6 7

3

3 1

1

1 4

4

3

5

Algoritmo de Dijkstra -...