Grafos - Parte 2

Vista previa del material en texto

Algoritmos y Estructuras de 
Datos
Departamento de Informática
LAS - TUP
Unidad N° 6: Grafos - Parte II
Motivación
1. Introducción a conceptos de grafos.
2. Tipo abstracto de Datos.
3. Implementación.
4. Utilización.
Repaso
● Definición
● Propiedades
● Tipos de grafos
● Representaciones
Introducción
Un problema relacionado con la búsqueda de caminos en grafos dirigidos es el 
problema del Camino más Corto (Shortest Path Problem).
Encontrar la mejor 
forma de ir desde un 
punto a otro (o a 
varios otros) 
minimizando la 
distancia recorrida, el 
tiempo invertido, entre 
varias posibilidades.
La representación 
más usual de este 
tipo de problemas 
(ya sea para
aplicarlo en 
problemas de camino 
mínimo o no) es la 
de grafos.
Definición del problema
Sea un grafo dirigido G=(V,A) ponderado, donde cada arco tiene un costo 
asociado no-negativo y un vértice (de V) es nombrado como origen; 
El problema del Camino más Corto consiste en determinar el camino más corto 
(en término de costos), desde el vértice origen a TODOS los demás vértices de V.
* Un camino se considera más corto que otro, cuando la suma de costos 
asociados a los arcos del primer camino es menor al segundo.
¡Problema importante!
Algoritmo de Dijkstra
Un algoritmo de tipo constructivo y goloso (o ávido) conocido para obtener los 
caminos más cortos desde un origen dado, es el algoritmo de Dijkstra (1956).
Sirve para cualquier grafo con pesos (dirigido o no) siempre y cuando sus 
pesos no sean negativos.
A partir de un conjunto S de vértices cuyos caminos desde el vértice origen son 
los más cortos, el algoritmo va agregando vértices a S, cuyos caminos a ellos se 
forme SOLAMENTE con los vértices de S.
Una vez que todos los vértices están en S, se habrán obtenido todos los caminos 
más cortos desde el vértice origen a los demás vértices.
Ejemplo
Ejemplo
S = {1} π = (0, ∞, ∞, ∞, ∞, ∞)
Ejemplo
S = {1} π = (0, 4, 7, ∞, ∞, 3)
Ejemplo
S = {1, 6} π = (0, 4, 7, ∞, ∞, 3)
Ejemplo
S = {1, 6} π = (0, 4, 7, ∞, ∞, 3)
Ejemplo
S = {1, 6} π = (0, 4, 7, ∞, 6, 3)
Ejemplo
S = {1, 6, 2} π = (0, 4, 7, ∞, 6, 3)
Ejemplo
S = {1, 6, 2} π = (0, 4, 7, ∞, 6, 3)
Ejemplo
S = {1, 6, 2} π = (0, 4, 7, ∞, 5, 3)
Ejemplo
S = {1, 6, 2, 5} π = (0, 4, 7, ∞, 5, 3)
Ejemplo
S = {1, 6, 2, 5} π = (0, 4, 7, ∞, 5, 3)
Ejemplo
S = {1, 6, 2, 5} π = (0, 4, 7, 9, 5, 3)
Ejemplo
S = {1, 6, 2, 5, 3} π = (0, 4, 7, 9, 5, 3)
Ejemplo
S = {1, 6, 2, 5, 3} π = (0, 4, 7, 9, 5, 3)
Ejemplo
S = {1, 6, 2, 5, 3} π = (0, 4, 7, 8, 5, 3)
Ejemplo
S = {1, 6, 2, 5, 3, 4} π = (0, 4, 7, 8, 5, 3)
Ejemplo
¿Costo del nodo 1 al nodo 5?
Ejemplo
Ejemplo
¿Qué devuelve el algoritmo?
Algoritmo
Dijkstra()
{ D es de tipoLista, C de tipoMatriz }
S={1} { vértice inicial }
Para i=2 hasta n
D[i]=C[1,i]
Para i=1 hasta n-1
Elegir un vértice w desde V-S tal que D[w] sea mínimo
Agregar w al conjunto S
Para cada vértice v en V-S
D[v]=min(D[v],D[w]+C[w,v])
Nota: n corresponde al grado del grafo. En tanto, el vértice inicial no necesariamente debe ser el primero.
Caminos más Cortos
Supongamos que ahora debemos obtener los caminos más cortos entre dos 
vértices cualesquiera de V.
Caminos más Cortos
Supongamos que ahora debemos obtener los caminos más cortos entre dos 
vértices cualesquiera de V.
Una alternativa puede ser invocando al algoritmo de Dijkstra cambiando en cada 
llamada, el vértice origen.
Caminos más Cortos
Supongamos que ahora debemos obtener los caminos más cortos entre dos 
vértices cualesquiera de V.
Una alternativa puede ser invocando al algoritmo de Dijkstra cambiando en cada 
llamada, el vértice origen.
Otra, mediante el algoritmo de Floyd.
Algoritmo de Floyd
Supongamos que los vértices (de V) están numerados de 1 a n.
Usando una matriz A de orden n, el algoritmo calcula los costos de los caminos 
(Dijkstra usa una lista . . . ).
Al comenzar, la matriz A se inicializa con los costos C[i,j].
Luego, al final de la iteración k-ésima (en total n iteraciones), en A[i,j] se tendrá el 
menor costo del camino que une a los vértices i y j (y que no pase dicho camino 
por algún vértice con índice mayor a k).
Algoritmo de Floyd
En la k-ésima iteración, la matriz A actualizar sus costos de la siguiente manera:
Ak [i, j]=Min(Ak-1[i,j ], Ak-1[i,k]+Ak-1[k,j ])
Es decir, en la etapa k, el menor costo (del camino) entre los vértices i y j, es el 
costo directo o bien el costo de ir desde i a k y luego de k a j.
Ejemplo
Ejemplo
Ejemplo
Ejemplo
Ejemplo
Ejemplo
Algoritmo
Floyd()
{A y C son de tipoMatriz}
Para i=1 hasta n
Para j=1 hasta n
A[i,j]=C[i,j]
Para i=1 hasta n
A[i,i]=0
Para k=1 hasta n
Para i=1 hasta n
Para j=1 hasta n
Si A[i,k]+A[k,j]<A[i,j] entonces
A[i,j]=A[i,k]+A[k,j]
Ejemplo
Sobre Camino más corto
El algoritmo de Dijkstra obtiene el camino más corto desde un vértice inicial 
cualesquiera, hacia el resto. Su complejidad es O(n2), siendo n el cardinal de 
vértices.
Si el cardinal de arcos es mucho menor que n2, puede mejorar a O(log (n)).
● El algoritmo de Floyd obtiene el camino más corto entre dos vértices 
cualesquiera del grafo. Su complejidad es O(n3). Bajo determinadas 
circunstancias, puede mejorar hasta O(nlog(n)).
● La aplicación del camino más corto a problemas de la vida real es amplia. .
Sobre Camino más corto
Obtuvimos las distancias.
 ¿Los caminos?
S = {1, 6, 2, 5, 3, 4} π = (0, 4, 7, 8, 5, 3)
Sobre Camino más corto
Obtuvimos las distancias.
 
S = {1, 6, 2, 5, 3, 4} π = (0, 4, 7, 8, 5, 3)
1-4
1-7
1-7
2-5
3-8
Sobre Camino más corto
Obtuvimos las distancias.