departamento informática aplicada - alejandro morán · informática aplicada algorítmica y...

DepartamentoInformáticaInformáticaAplicada

Algorítmica y Complejidad

Tema 3 – Algoritmos sobre GrafosTema 3 Algoritmos sobre Grafos

Curso 2012-13

Grafos

1 Conceptos Definiciones y Representación1. Conceptos, Definiciones y Representación

2 Conectividad y recorrido2. Conectividad y recorrido

3 Árboles de expansión3. Árboles de expansión

4 Caminos mínimos4. Caminos mínimos

2

Grafos

11.




3

Conceptos, Definiciones y RepresentaciónEl origen de la teoría de grafos ...

El problema de los puentes de Königsberg (1736)¿es posible dar un paseo comenzando desde cualquiera de estas

i d t d l t i d ólregiones, pasando por todos los puentes, recorriendo sólo una vez cada uno, y regresando al mismo punto de partida?

Resuelto por EulerllNo hay solución•Se puede comprobar utilizando “fuerza bruta”D t ió d E l

Grafos 4

•Demostración de Euler

Conceptos, Definiciones y RepresentaciónEjemplos

– Redes de transporte (carreteras, rutas aéreas, ...)– Redes de comunicación (Internet)

R d d i f ió (WWW)– Redes de información (WWW)– Redes sociales (Facebook, Twitter, FourSquare, ...)

– Dependencias (asignaturas pre-requisito, diagramas de flujo, ...)

D fi i ió f l d fDefinición formal de grafo– Par de conjuntos G=(V, E)

• V nodos y E aristas• V nodos y E aristas• Cada arista es un par (u,v) con u,v V• Si el par está ordenado es un grafo dirigidop g g• Si no está ordenado es un grafo no dirigido

Grafos 5

Conceptos, Definiciones y Representación

• Grado del grafo (grado G )g (g )– Número de nodos / vértices |V|

• Nodos adyacentes– Si están unidos por una arista

• Grado de un nodo (grado u )– Número de aristas que inciden en un nodo ó número de nodos

adyacentesHandshaking Lemma–

– En grafo dirigido: grado de entrada y grado de salida

C ( )

Handshaking Lemma

• Camino entre dos nodos (path u,v )– Secuencia de nodos, tal que dos nodos consecutivos son

adyacentes (uxi xixi 1 xi 1xi 2 xi v)adyacentes (uxi, xixi+1, xi+1xi+2, ...., xi+nv)– Es simple cuando no hay nodos repetidos en el camino– Ciclo es un camino simple pero con u = v

6Grafos

• Grafo conexo


Grafo conexoCada par de nodos está conectadopor un camino

• Grafo no conexoNo existe un camino que una unnodo con los demásNo existe un camino entre a y ey

• Bosque–Grafo sin ciclos

• Árbol libre–Bosque conexo

–Con un nodo en el papel de raíz

7Grafos


• Siempre se cumple que:

a.b.Si G es conexo, |E| |V|-1

Si G á b l |E| |V| 1c.Si G es árbol, |E| = |V|-1d.Si G es bosque |E| |V|-1

• Describir este grafo (grid)

1 Di i id di i id1. ¿Dirigido o no dirigido2. ¿Conexo?3. ¿Bosque?4 Grado de los nodos4. Grado de los nodos

Grafos 8


Representación de grafosRepresentación de grafos• Listas de adyacencia

1

5

2

4

3 G=(V,E)

5 4 Las aristas pueden tener pesos asociados.

• Grafos poco densos |E| << |V|21 2 5 |E| |V| Espacio (|V|+|E|)

• Si el grafo es dirigido

1

2

3

2

1

2

5

5

4

3 4

• Si el grafo es dirigido list[i].length = |E|

Si l f NO di i id

3

4

5

2

2

4

4

5

1

3

2 • Si el grafo es NO dirigido list[i].length = 2*|E|

5 4 1 2

Grafos 9

• Longitud total de la lista (|E|)


Representación de grafosRepresentación de grafos• Matriz de adyacencia

1

5

2

4

3 G=(V,E)

5 4 Las aristas pueden tener pesos asociados.

1 2 3 4 51 2 3 4 51 0 1 0 0 12 1 0 1 1 1

• Grafos densos |E| ≈ |V|2 Un solo bit por arista

3 0 1 0 1 04 0 1 1 0 1

Un solo bit por arista Espacio (|V|2)

C lt b i t5 1 1 0 1 0 • Consultas sobre aristas

Grafos 10

Grafos


22.



11

Conectividad y RecorridoDado un grafo G=(V,E) y dos nodos s y t

– Problemas: ¿Existe un camino para llegar de s a t?¿A qué distancia están?

– Concepto de distancia entre dos nodos s y t como (s, t)• Mínimo número de aristas entre s y t.

– Breadth-First Search (BFS)• Recorrido en amplitud. Dado un nodo s, primero visita todos los

nodos a distancia 1 (L1) de s, luego a distancia 2 (L2), y así sucesivamente.

• Li(s) Conjunto de nodos a distancia i de s

– Depth-First Search (DFS)• Recorrido en profundidad. Dado un nodo s, visita el primer nodo

conectado a s y después el primer nodo conectado al últimoconectado a s y después el primer nodo conectado al último visitado

Grafos 12

Conectividad y Recorrido

Breadth-First SearchBreadth First Search 1

2 3

7

84 5

6BFS (G, s = 1)

1 1 1

( , )

L2

L12 3 2 3

4 5 7 8

2 3

4 5 7 8

L3

L2 4 5 7 8 4 5 7 8

6

Grafos 13

Conectividad y Recorrido• BFS (G, s) - Implementación

– s y u están conectados si u Lj con j ≥ 1– Visitados Lista con los nodos visitados

BFS G, s :Visitados s true, u s Visitados s falseL 0 L 0 s , i 0, T Ø T: Árbol generado por BFS (lista while L i Ø doL i 1 Ø foreach u in L i do No hay orden al procesar L

de aristas de los nodos accesibles desde el nodo s)

foreach v in G doif G.Matriz u,v 0 & Visitados v false then

Visitados v true

¿Existe la arista (u, v) y v no ha sido visitado todavía?

Añadir la arista en el árbol TT T u, vL i 1 L i 1 v

endif

Añadir la arista en el árbol T

Incluir el nodo encontrado

endforendfori i 1

Complejidad O(|V|2)

Con listas de adyacencia O (|V|+|E|)

Grafos 14

endwhiley (| | | |)

Conectividad y Recorrido• Complejidad de BFS

– Un nodo sólo puede aparecer en una lista (Li)– Por lo tanto el bucle foreach se ejecuta n |V| veces– Cada iteración del bucle se ejecuta n veces, se

consideran todos los nodos– Un cota es O n2

– Una cota mejor:• Utilizando listas de adyacencias en lugar de matriz• El procesamiento de cada nodo u puede optimizarse si tiene

pocos vecinos• La longitud de la lista de adyacencia es 2*m, m |E|La longitud de la lista de adyacencia es 2 m, m |E|• El bucle foreach se ejecutará m veces• Para manejar Li y Visitados se emplea O n• Una cota mejor es O m n

Grafos 15


Depth-First Search 1 7Depth First Search2 3

84 5

Procesamiento de izda a dcha Procesamiento de dcha a izda6

Procesamiento de izda. a dcha.

1

Procesamiento de dcha. a izda.

1

2

43

35

67 5

68 48 6

Grafos 16

7 2


• DFS (G, s) – Implementación (no recursiva)( , ) p ( )– Utilizando una pila (S) para procesar los nodos– Visitados: Lista con los nodos visitados

DFS G, s : i V, Visitados i false

h S C l jid dpush S, swhile S Ø dou pop S

Complejidad•Añadir y borrar un nodo de S, O 1El ú d i Su pop S

if Visitados u false thenVisitados u true

•El número de operaciones en Sacotado por el grado de G, O |E|•Operaciones en la lista acotadas

foreach v in G.Adyacencia u dopush S, vdf

Operaciones en la lista acotadas por |V|

•O |E| |V| utilizando listas de endforendif

endwhile

| | | |Adyacencia

Grafos 17

endwhile

Conectividad y Recorrido• DFS (G, s) – Implementación (recursiva)

– Visitados Lista con los nodos visitados– R Lista de elementos conectados desde un nodo dado– T Árbol DFS– T Árbol DFS

1

2 3

7

DFS G, u :Visitados u trueR R

84 5R R uforeach v in G.Adyacencia u doif Visitados v false then

6Li t d Ad iif Visitados v false then

T T u,vDFS G, v

Lista de Adyacencias1. 2, 32. 1, 3, 5, 43. 5, 7, 8, 1, 2

endifendfor

3. 5, 7, 8, 1, 24. 2, 55. 4, 6, 2, 36. 57 8 3

Grafos 18

7. 8, 38. 7, 3

Conectividad y RecorridoGrafos Dirigidos

– Con BFS y DFS comprobamos la existencia de un camino entre dos nodos s y tAunque exista el camino puede que no exista entre t y s– Aunque exista el camino, puede que no exista entre t y s

– Un grafo está fuertemente conectado si:• s, t V, existe un camino entre s y t y entre t y sy y y

A BA B

DC

Fuertemente conectado DC E

• Algoritmo:

Fuertemente conectado

NO fuertemente conectadog1.BFS (G, s) ó DFS (G, s)2.Calcular Grev (Invertiendo el sentido de las artistas)3.BFS (Grev, s) ó DFS (Grev, s)

Grafos 19

3.BFS (G , s) ó DFS (G , s) 4.Si BFS ó DFS fallan y no alcanzan todos los nodos, el grafo NO está fuertemente conectado


Grafos DirigidosGrafos Dirigidos– Sin ciclos es un DAG (Directed Acyclic Graph)– Los DAG aparecen con bastante frecuencia– Los DAG aparecen con bastante frecuencia

• Relaciones de precedencia o dependencia– Si se puede establecer un orden entre los nodos, de tal forma queSi se puede establecer un orden entre los nodos, de tal forma que

(u, v) E y u < v (orden), entonces G tiene orden topológico.– Si G es un DAG, entonces tiene orden topológico

MD

ALGFP SD ALG SDFPED MD SOPOOC

ED SO POOC

Posible precedencia de las

Orden topológico de las asignaturas

Grafos 20

Posible precedencia de las asignaturas de Grado

Conectividad y RecorridoAlgoritmo de ordenación topológica 2 3

– R Lista con la ordenación (resultado)– Complejidad O n2 56 4

ORDENACION_TOPOLÓGICA G :Encontrar un nodo u / v V, v, u ER R

7 1

R u RG.V G.V uif G.V Ø then

5

2

6

3

4if G.V Ø thenORDENACION_TOPOLÓGICA G

endif 7

R 1

3 56 4

66 7

56

7

4 7

R 1, 2, 3

56

77

R 1 2 3 4 5

R 1, 2, 3, 4, 5, 6

R 1, 2, 3, 4, 5, 6, 7

Grafos 21

R 1, 2 R 1, 2, 3, 4R 1, 2, 3, 4, 5

Grafos





22

Árboles de Expansión¿Cómo conectar todos los nodos con el mínimo coste?

B C D8 7

4 9w(T) w(u,v), T E

A I E

4

8

117

2

4 14

9

106

(u,v)T

w : E

H G F10

21

B C D8 7

Aplicaciones

A I E

4 2

4

9Aplicaciones•Logística•Conexionado

Ciudades

C t 37

H G F21

Ciudades, Componentes eléctricos, Personas, etc.

•Enrutamiento en redesCoste 37Algoritmos de construcción (Voraces)

•Genérico•Kruskal

Se puede sustituir (B,C) por (A,H) con igual coste

Grafos 23

•Prim

Árboles de ExpansiónPropiedades de los arboles de expansión:

– Tienen |V|-1 arcos– No tienen ciclos

P d ú i– Pueden no ser únicos

MST_GENERICO G, w : // Minimum Spanning TreeA Ø # Conjunto de arcos que forman el MSTA Ø # Conjunto de arcos que forman el MSTwhile A no forme Minimum Spanning Tree do Encontrar un arco e E, f E, / w e w f && A e sea acíclico /A A eE E ‐ e

donereturn A

Añ d d l á b l d ió (A)– Añade un arco cada vez al árbol de expansión (A)– Finaliza cuando todos los nodos están conectados– El problema es comprobar que no se añaden ciclos

Grafos 24

El problema es comprobar que no se añaden ciclos

Árboles de ExpansiónAlgoritmo de Kruskal• Descripción

– Algoritmo voraz, en cada iteración añade un arco de peso mínimo– Utiliza dos conjuntos:

• Un bosque F, que inicialmente contiene un árbol por cada vértice V• Un conjunto S con los arcos del grafo G (inicialmente S = G.E)Un conjunto S con los arcos del grafo G (inicialmente S G.E)

– Mientras S contenga arcos y F no sea un árbol de expansión• Extraer de S el arco de peso mínimo (u,v)

Si ( ) d b l dif t ñ di l F bi l• Si (u,v) une dos arboles diferentes, añadir el arco a F y combinar los dos arboles en uno

– Al final del proceso F contiene un único componente que forma un árbol de expansión

– El coste de ordenar S es O (m log m), siendo m = |E|– Al existir al menos un arco entre cada par de nodos p

• m n2 m n* n‐1 /2 Grafo no dirigido conexo• lg m O lg n lg n2, 2*lg n O lg n • La cota es O m log n• La cota es O m log n

Grafos 25

Árboles de Expansión

Algoritmo de Kruskal• Ejemplo (1/2)

g

2 311

2 31

2 31

5

2

6

3

4

4 53

19

15

2

6

3

4

4 53

19

15

2

6

3

4

4 53

19

1

7 12

6

37 1

2

6

37 1

2

6

3

2 34 5

3 1

2 34 5

3 1

2 34 5

3 1

1 1 1

56

7

4

12 3

1956

7

4

12 3

1956

7

4

12 3

19

6 6 6

¡CICLO! Los nodos 2 y 5 pertenecen al

mismo árbol

Grafos 26

mismo árbol


Algoritmo de Kruskal• Ejemplo (2/2)

g

2 3 2 3 2 31 1 1

5

2

6

3

4

4 53

19

15

2

6

3

4

4 53

19

15

2

6

3

4

4 53

19

1

7 12

6

37 1

2

6

37 1

2

6

3

Coste 12Coste 12

• ImplementaciónMediante conjuntos para representar los diferentes arboles– Mediante conjuntos para representar los diferentes arboles

– Estructura de datos para manejar conjuntos disjuntos (Union‐Find)– Operaciones sobre conjuntos:p j

• Make‐Set u• Union u, v• Find u

Grafos 27

• Find u

Árboles de ExpansiónEstructura de datos Union‐Find

– Find u devuelve el conjunto al que pertence el nodo u– Para comprobar si un arco (u,v) genera un ciclo:

if Fi d Fi d th• if Find u Find v then ......– Para combinar dos arboles mediante el arco (u,v):

• Union u, vUnion u, v

cab

S1

cab

S2

a bcab

cola c dcab

cola e

Arcos Conjunto BAArcos Conjunto(a,b) {a, b}(c,d) (d,e) {c, d, e}

BA

DC E

Grafos 28


Estructura de datos Union FindEstructura de datos Union‐Find– Union b, c

cab

S1

a bcola c d e

BA C

Arcos Conjunto(a,b) {a, b}

BA

D

C

Dos arboles(c,d) (d,e) {c, d, e}(a,b) (b,c) (c,d) (d,e) {a, b, c, d, e } E

Dos arboles

Un único árbol

Grafos 29

Árboles de ExpansiónAlgoritmo de Kruskal

Utilizando la estructura Union Find– Utilizando la estructura Union‐Find– A: conjunto con los arcos que forman el MST– W: lista ordenada de arcos por peso

MST‐KRUSKAL G, w :A Øf h i G V d // d dforeach v in G.V do // cada nodo un conjuntoMake‐Set v

endforendforW Ordenar Ascendente, G.E, wwhile A MST do

Para comprobar A MST•Un único conjunto Union‐Find

u,v ExtraerPrimerArco Wif Find u Find vA A

j•Todos los nodos V conectados

A A u, vUnion u, v

endif

Grafos 30

endifendwhile

Árboles de ExpansiónAlgoritmo de Prim• Descripción

– Variante del algoritmo genérico– Algoritmo voraz, en cada iteración añade un arco de peso mínimo– Mantiene un único árbol (en cambio, Kruskal un bosque)– Utiliza dos conjuntosUtiliza dos conjuntos

• A para almacenar los arcos que forman el MST• S nodos que forman parte del MST

Mi t G V S Ø– Mientras G.V − S Ø• Escoger el arco de peso mínimo u, v tal que u S y v G.V − S• Añadir (u, v) al conjunto A• Añadir a S el extremo de (u, v) que no pertenece a S

– Cotas• Con matrices de adyacencia es O V2• Con matrices de adyacencia es O V2

• Con colas y listas de adyacencia para implementar S es O V E lg V• Con montículos de Fibonacci y listas de adyacencia es O E V lg V

Grafos 31


Ej lAlgoritmo de Prim• Ejemplo

2 34 5

3 1

2 34 5

3 1

2 34 5

3 1

1 1 1

56

7

4

12 3

3

19

156

7

4

12 3

3

19

156

7

4

12 3

3

19

1

7 16

7 16

7 16

2 34 5

1 2 34 5

1 2 34 5

1

56 4

4 5

2 3

3

19

156 4

4 5

2 3

3

19

156 4

4 5

2 3

3

19

1

7 12

6

37 1

2

6

37 1

2

6

3

2 34 5

1

56 4

4 5

2 3

3

19

1

Grafos 32

7 12

6

3


Algoritmo de PrimAlgoritmo de Prim

– El tiempo de ejecución del algoritmo depende de la búsqueda del arco de peso mínimo

– Para cada nodo se añaden las informaciones:• key Para mantener ordenados los nodos• parent Nodo padre en el árbol de expansión

– Q mantiene ordenados los nodos de acuerdo a key Q a t e e o de ados os odos de acue do a ey– A guarda el MST A v, v.parent : u V – r – Q

Grafos 33

Árboles de ExpansiónAlgoritmo de Prim

MST‐PRIM G, w, r :foreach u in G V do

while Q Ø dou EXTRACT MIN Q ¡¡ Crítico !!foreach u in G.V do

u.key u parent NIL

u EXTRACT‐MIN Qforeach v in G.Adyacencia uif v Q && w u v v key

Inicialización

¡¡ Crítico !!

u.parent NILendfork 0 # N d í

if v Q && w u, v v.keyv.parent ukr.key 0 # Nodo raíz

Q G.Vv.key w u, vA A v, v.parentdifendif

endfor d h lendwhile

Grafos 34

Árboles de ExpansiónAlgoritmo de Prim A

– Seguimiento (1/2)A B

2

3

Nodo Adyac. Key ParentA B C 0 NIL

V ‐ A

C D

1 3

4

A B, C 0 NILB A, D NILC A, D NIL

Q = {A, B, C ,D}

D B, C NIL


Q = {B, C ,D} A B2

A B, C 0 NILB A, D 2 AC A, D 1 A

u = A, v = B, v = C

C D

1 3

4D B, C NIL


Q = {B, D}C A D

A B

4

2

A B, C 0 NILB A, D 2 AC A, D 1 A

u = C, v = A, v = D

C D

1 3

4

Grafos 35

D B, C 4 C4

Árboles de ExpansiónAlgoritmo de Prim Seguimiento (1/2) A

Nodo Adyac. Key ParentA B, C 0 NIL

Q = {B, D}u = C v = A v = D

2

V \ A

A B2

B A, D 2 A

C A, D 1 AD B C 4 C

u C, v A, v D

C D

1 3

D B, C 4 C

Nodo Adyac. Key ParentA B, C 0 NIL Q = {D}

B A D

4

A B2

C D4

B A, D 2 A

C A, D 1 AD B C 4 3 C B

u = B, v = A, v = D A B

1 3

D B, C 4 3 C B

Nodo Adyac. Key ParentQ {Ø}

C D4

A B2

A B, C 0 NILB A, D 2 AC A D 1 A

Q = {Ø}u = D, v = B, v = C

C D

1 3

Grafos 36

C A, D 1 AD B, C 3 B

C D4

Árboles de ExpansiónAnálisis del algoritmo de Prim

MST‐PRIM G, w, r :foreach u in G.V do

u keyu.key u.parent NIL

endforr key 0 # Nodo raíz

V

r.key 0 # Nodo raízQ G.V

while Q Ø dowhile Q Ø dou EXTRACT‐MIN Qforeach v in G.Adyacencia u

if Q && k Decrementar / Eif v Q && w u, v v.keyv.parent uv.key w u, vA A

|V| veces Grado(u) veces

Decrementar / ET cte

A A u, u.parentendif

endfor

vecesImplícito

Grafos 37

endwhile

Árboles de ExpansiónMST‐PRIM G, w, r :

foreach u in G V doforeach u in G.V dou.key u.parent NIL

endfor V endforr.key 0 # Nodo raízQ G.V

while Q Ø dou EXTRACT‐MIN Qf h i G Ad iforeach v in G.Adyacencia u

if v Q && w u, v v.keyv.parent uk

|V| veces Grado(u)

Decrementar / ET cte

v.key w u, vA A u, u.parent

endif

| | Grado(u) veces

Implícito

endforendwhile

Tiempo = V * T E * T

Grafos 38

Tiempo = V * TEXTRACT_MIN E * TDECREMENTAR_KEY


• Análisis del algoritmo de PrimAnálisis del algoritmo de Prim– TEXTRACT_MIN y TDECREMENTAR_KEY depende de la estructura de datos

utilizada para implementar el conjunto Q– TTOTAL = V * TEXTRACT_MIN E * TDECREMENTAR_KEY

Q TEXTRACT MIN TDECREMENTAR KEY TTOTALQ TEXTRACT_MIN TDECREMENTAR_KEY TTOTAL

array O(V) O(1) O(V2)Binary heap O(lg V) O(lg V) O(E lg V)Fibonacci

HeapO(lg V)

amortizadoO(1)

amortizadoO(E + V lg V)

Peor caso

Grafos 39

Grafos





40

Caminos mínimos

El problema: ¿Cuál es la forma más rápida de ir .... ?p ¿ p– Camino mínimo

También

¿Cuál es la más barata?¿

¿Cuál es la de menor distancia recorrida?distancia recorrida?

A B1

C

D

51

22

4F

E

D

3

4

1

Grafos 41

2 caminos mínimos

Caminos mínimos

Variantes del problemaVariantes del problema

•BFS caminos mínimos en grafos no ponderados– Todos los enlaces con el mismo peso

•Caminos mínimos a un destino desde el resto de nodos•Caminos mínimos para todos los pares de nodos

Una posible solución: calcular el camino mínimo para– Una posible solución: calcular el camino mínimo para cada nodo

Grafos 42

Caminos mínimos

DefinicionesDefiniciones•Se parte de un grafo dirigido y ponderado

G V E ER– G V,E y w: ER

w p es el peso del camino p v v v•w p es el peso del camino p v0, v1, ... vk

w(p) w(vi1,vi )k

• u, v es el peso del camino mínimo entre u y v

i1

p y

(u, v) min {w(p) : u P v} Si existe un camino entre u y v(u, v)

No hay camino

Grafos 43

Caminos mínimos

Técnica de la relajación de arcosj•Asignar peso y predecesor a cada vértice/nodo

– Peso al origen (v.d), inicialmente a infinito– Predecesor (v.p), nodo previo en el camino

•Técnica de “Relajamiento”

Ad=5

Bd=9

2

f d A d A hRELAX

if B.d A.d w A, B thenB.d A.d w A,BB p A

Ad=5

Bd=7

2B.p A

Grafos 44

Caminos mínimosAlgoritmo de Bellman-Ford

– Camino mínimo a todos los nodos desde una fuente s– Permite pesos negativos

Devuelve los caminos mínimos y sus pesos asociados– Devuelve los caminos mínimos y sus pesos asociados– Complejidad O (|V|*|E|) (2 bucles anidados)

BELLMAN FORD G w sBELLMAN‐FORD G, w, s :INIT‐SINGLE‐SOURCE G, sforeach n in 1 to |G.V‐1| dof h i G E d

INIT‐SINGLE‐SOURCE G, sforeach v in G.V dov d∞foreach u, v in G.E do

RELAX u, v, wendfordf

v.d ∞v.p NIL

endfors d 0

Relaja todas las aristas |V-1| veces

endforforeach u, v in G.E doif v.d u.d w u, v

s.d 0

Evitar ciclos RELAX u, v, wif v.d u.d w u, v

return FALSEendif

endfor

negativos,

v.d u.d w u, vv.p u

endif

Grafos 45

return TRUE

Caminos mínimos

Algoritmo de Bellman-Fordg

D=∞A

D=∞3 D=∞B

D=∞-1

D=3A

D=33 D=∞B

D=∞-1

relaxD=0

SD=0

C D2

2-1 4

D=0S

D=0C D2

2-1 4

relax

relaxD=∞D=∞ D=∞D=∞1 D=2D=2 D=∞D=∞1

D=3A

D=3

S

3 D=2B

D=2-1

2 4

D=3A

D=3

S

3 D=2B

D=2-1

21 4

D=0S

D=0

D=2C

D=2 D=6D

D=62

1

2-1 4

D=0D=0

D=2C

D=2 D=3D

D=32

1

-1 4

1

“Relaja (C,D)”δ(S, A) = 3 δ(S,C) = 2

Grafos 46

δ(S, B) = 2 δ(S,D) = 3

Caminos mínimos

Algoritmo de Bellman-Ford (Con arcos de peso Negativo)Algoritmo de Bellman Ford (Con arcos de peso Negativo)– Problema: No encontrar el camino mínimo en presencia de ciclos

D=3A

D=3-4

D= 1B

D=-1 δ (S,A) = w(S,A) = 3

C6

DS G

3

5 8

4 δ (S,B) = -1

Para (S,C) hay infinitos caminos( ) ( d )d=5 d=11d=11

-3D=0D=0 d= ∞d=-∞

27

(s,c), (s,c,d,c) .....pero sólo uno de peso mínimoδ (S,C) = w(S,C) = 5

d= ∞E

d=-∞

3

d= ∞F

d=-∞-6

Para (S,E) hay infinitos caminos(s,e), (s,e,f,e), (s,e,f,e,f,e) ....NO existe un camino mínimoNO existe un camino mínimoδ (S,E) = -∞Ídem para (S,F) y (S,G)Cuantas más vueltas menor peso

Grafos 47

Caminos mínimos

Al it d Dijk tAlgoritmo de Dijkstra

– Grafos dirigidos con pesos no negativos– Explorar todos los caminos más cortos desde la fuente– Estrategia voraz– S conjunto de nodos cuyo camino ya ha sido obtenido– Q Montículo Min ordenado por v.d– Más rápido que el algoritmo de Bellman-Fordp q g

• Con Montículo Min, O ( (|V|+|E|) log |V|)• Sin utilizar Montículo, O (|V|2) , (| | )

Grafos 48

Caminos mínimos

DIJKSTRA G w s :DIJKSTRA G, w, s :INIT‐SINGLE‐SOURCE G, sS ØS ØQ G.Vhil Q Ø d

u tiene d (distancia) menor a la fuente (s)while Q Ø do

u EXTRACT‐MIN QS S

menor a la fuente (s),en el conjunto V − S

S S uforeach v in G.Adyacencia u do

RELAXRELAX u, v, wendford h lendwhile

Grafos 49

Caminos mínimosAlgoritmo de Dijkstra Nodos en S

31

P=

AD=∞P= P=

BD=∞P=

S

31

2P=S

AD=3P=S P=

BD=∞P=

relax

P=

SD=0P=

2

21 4

CD=∞

DD=∞

P=

SD=0P=

2 1

21 4

CD=2P=S

DD=∞

relax2 1P=P= P=

DP=

1P=SP=S P=P=

1AD=3

BD=∞ 3

1AD=3

BD=4relax

SD=0P

3

21 4

P=SD 3P=S P=

DP=

C

SD=0P=

3

21 4

P=SP=S P=AP=A

C D

relax

P=P=

2 1P=S

CD=2P=S P=C

DD=3P=C

P=P=

2 1P=S

CD=2P=S P=C

DD=3P=C

31A

D=3P=S

BD=4P=A

relax

P=

SD=0P=

21 4

P=SP=S P=AP=A

CD 2

D¿Existe algún

camino alternativo?

Grafos 50

2 1P=SD=2P=S P=C

D=3P=C

camino alternativo?

Caminos mínimosAlgoritmo de Dijkstra Nodos en S

31A

D=3P=S

BD=∞P=

31A

D=3P=S

BD=4P=D

P=

SD=0P=

21 4

P=SP=S P=P=

C DP=

SD=0P=

21 4

P SP S P DP D

CD 2

Drelax

relax

2 1P=SD=2P=S P=C

DD=3P=C

2 1P=SD=2P=S P=C

D=3P=C

relax

31A

D=3P S

BD=4P D

P=

SD=0P=

3

21 4

P=SP=S P=DP=D

C D

relax

2 1P=SD=2P=S P=C

DD=3P=C

Grafos 51

departamento informática aplicada - alejandro morán · informática aplicada algorítmica y...

Documents