An Lisis De Algoritmos 2

ANÁLISIS DE ALGORITMOS
Nº 2

a

b
c

d

Grafos

1

2

45
5

e

10

25

40

55
30

25
50

4

15

20
3

INTRODUCCIÓN

• Los grafos se usan para modelar problemas
definidos en términos de relaciones o
conexiones entre objetos.
• Tienen un amplio uso en ingeniería para
representar redes de todo tipo:
– transporte (tren, carretera, avión),
– servicios (comunicación, eléctrica, gas, agua),
– deactividades en el planeamiento de proyectos,
etc.

¿QUÉ ES UN GRAFO?
• Un grafo G = (V, E) está compuesto de:
V : conjunto de vértices o nodos
E : conjunto de aristas o arcos que
conectan los vértices en V


Una arista e = (v, w) es un par de vértices



Ejemplo:
a

b

V = { a, b, c, d, e}

e

E = { (a, b), (a, c), (a,d),
(b, e), (c, d), (c, e),
(d, e) }

c
d

APLICACIONES




Grafo detransiciones (AFD)
b
inicio

0

2

b
a

Coruña

b

1

2

b

a

3

4
Sevilla

a


Planificación de tareas
(Pert/CPM)
inicio

A(3)

I(1)

D(2)
C(4)

B(2)

E(3)

final

Santander
1

2

a



Tiempo de vuelos aéreos
2

Barcelona

1

Madrid
2

2
3

Valencia

Grafo asociado a un dibujo de
líneas (visión artificial)

DEFINICIONES

• Arista dirigida: par ordenado (u, v)
u


Arista no dirigida: par no ordenado(u, v)
u





v

v

Grafo dirigido o digrafo: grafo cuyas aristas son todas
dirigidas.
Grafo no dirigido o grafo: grafo cuyas aristas son
todas no dirigidas.
Grafo mixto: grafo con aristas dirigidas y no dirigidas.

DEFINICIONES
• Vértices finales o extremos de la arista: vértices unidos por una arista.
– Vértice origen: primer vértice de una arista dirigida.
– Vértice destino: segundo vérticede una arista dirigida.
• Arista incidente en un vértice: si el vértice es uno de los vértices de la
arista.
• Aristas salientes de un vértice: aristas dirigidas cuyo origen es ese vértice.
• Aristas entrantes de un vértice: aristas dirigidas cuyo destino es ese vértice.

a

b

DEFINICIONES

• Vértices adyacentes: vértices finales de una arista.
– Un vértice w es adyacente a v sí y sólo si (v, w)(ó (w, v)) pertenece a E.
– En grafos no dirigidos la relación de adyacencia es
simétrica.
– En grafos dirigidos la relación de adyacencia no es
simétrica.
Vértices adyacentes:
a
b
c
d

e

a = { b, c, d }
b={e}
c = { a, d, e }
d = { a, c }
e={d}

ALGORITMO DE DIJKSTRA

Uno de los algoritmos más usados
para la búsqueda de caminos de peso
mínimo es el de Dijkstra, que
proporciona los pesos mínimosdesde
un vértice dado al resto de los vértices.

ALGORITMO DE DIJKSTRA
(ETIQUETAS)

[8,B](2)
DISTANCIA
ACUMULADA

DE DONDE O QUE
NODO PROCEDE

NÚMERO DE
ITERACIONES

ALGORITMO DE DIJKSTRA

1

A

[0,-](0)

3

[1,A](1)

F

2
B

5 [3,A](1)
G

5

C

1

[4,D](3) 2

[6,C](2)
[5,D](3)

3

2
D

[3,C](2)

1

4

[8,B](2) D A H = 8 A C D F H
O
A C D F H

E

H

[7,D](3)

[8,F](4)
[8,E](3)

ALGORITMO DEDIJKSTRA

1

A

[0,-](0)

3

[1,A](1)

F

2
B

5 [3,A](1)
G

5

C

1

[4,D](3) 2

[6,C](2)
[5,D](3)

3

2
D

[3,C](2)

1

4

[8,B](2) D A H = 8 A C D F H
O
A C D F H

E

H

[7,D](3)

[8,F](4)
[8,E](3)

EJERCICIO 1

4
S

B

1
2

5
8

D

6
T

2
2

C

10

E

D S T = 12
S C B D E T

EJERCICIO 2

DISTANCIA = 23
A D C B F E Z

ALGORITMO DE FLOYD
El algoritmo de Floyd-Warshall, descrito en 1959 porBernard Roy, es un algoritmo de análisis sobre grafos para
encontrar el camino mínimo en grafos dirigidos ponderados.

ALGORITMO DE FLOYD

3

B

PONDERACIÓN

5

8

A

4

C

D

3

-

3

4

∞

∞

-

∞

5

∞

∞

-

3

8

∞

∞

-

A

B

C

D

A

B

C

D

A

B

C

D

A

B

C

D

RECORRIDO

ALGORITMO DE FLOYD

3

B

PONDERACIÓN

5

8

A

4

C

D

3

1er Análisis: Fila y Columna A
Consideraciones:
NºNatural < ∞ = Nº Natural
La diagonal no debe cambiar nunca

-

3

4

∞

∞

-

∞

5

∞

∞

-

3

8

11
∞

∞

-

A

B

C

D

A

B

C

D

A

B

C

D

A

BA

C

D

RECORRIDO

ALGORITMO DE FLOYD

3

B

PONDERACIÓN

5

8

A

4

C

2do Análisis: Fila y Columna B

D

3

-

3

4

∞
8

∞

-

∞

5

∞

∞

-

3

8

11
∞

∞

-

A

B

C

B
D

A

B

C

D

A

B

C

D

A

BA

C

D

RECORRIDO

ALGORITMO DE FLOYD

3...