Upload
hernan-covarrubias
View
96
Download
0
Embed Size (px)
Citation preview
Caminos ms cortos a partir de mltiples fuentes en un grafoJoemmanuel Ponce Galindo
Qu es un grafo?
Un grafo es
Una pareja ordenada G(V,E) con las siguientes caractersticas: V es un conjunto de vrtices E es un conjunto de parejas de distintos vrtices, entre los cuales se trazan lneas (aristas)
1. 2.
Grafos ponderados22 4 1 1
131
45
3
3
1
5
Entonces
l(a) = peso de la arista a l(x,y) = peso de la arista de x a y
Y qu podemos modelar?2 1 2 0 3 4 1 7 1 5 2 6 1 1 3 3 1 4 1 1 1 1 9 2 1 8 1 3
15
3
1 1 21 2 1 1 6 2
9
1 0 4
5
8
3 5 8 1 3 0 6 4 7
Problema de la ruta mnima (Single Source)224 1 1
131
45
3
3
1
5
Cmo llego del punto 1 a 4 de la manera ms corta posible?
Cmo se resuelve?
Existen algoritmos genricos para ello:
Dijkstra Algorithm Floyd Algorithm Bellman-Ford Algorithm
Algoritmo de Dijkstra
Algoritmo glotn (greedy) Punto de inicio s Conjunto S Vector D1
22 1 1 3
4
45
1
3
3
1
5
Condiciones iniciales
S={1} V-S={2,3,4,5} D=[0,2,1,,3]1 2 3 4 5
22
4 1
11
45
1
3
3
3
1
5
El algoritmo
Aumentar S agregando el elemento v en V-S tal que Dv sea el mnimo de ese conjunto. Actualizar los valores de Di para todos los elementos i existentes en V-S. Di=mnimo( Di, Dv+f(v, i) ) Terminar cuando |S|=|V|
Paso a paso (Iteracin 1)
Buscar mnimo Di en V-S S={1} V-S={2,3,4,5} D=[0,2,1,,3]1 2 3 4 5
22
4 1
11
45
1
3
3
3
1
5
Paso a paso (Iteracin 1)
Agregar elemento a S. Actualizar D S={1,3} V-S={2,4,5} D=[0,2,1,,3]1 2 3 4 5
22
4 1
11
45
1
3
3
3
1
5
Paso a paso (Iteracin 2)
Buscar mnimo Di en V-S S={1,3} V-S={2,4,5} D=[0,2,1,,2]1 2 3 4 5
22
4 1
11
45
1
3
3
3
1
5
Paso a paso (Iteracin 2)
Agregar elemento a S. Actualizar D S={1,3,2} V-S={4,5} D=[0,2,1,,2]1 2 3 4 5
22
4 1
11
45
1
3
3
3
1
5
Paso a paso (Iteracin 3)
Buscar mnimo Di en V-S S={1,3,2} V-S={4,5} D=[0,2,1,6,2]1 2 3 4 5
22
4 1
11
45
1
3
3
3
1
5
Paso a paso (Iteracin 3)
Agregar elemento a S. Actualizar D S={1,3,2,5} V-S={4} D=[0,2,1,6,2]1 2 3 4 5
22
4 1
11
45
1
3
3
3
1
5
Paso a paso (Iteracin 4)
Buscar mnimo Di en V-S S={1,3,2,5} V-S={4} D=[0,2,1,6,2]1 2 3 4 5
22
4 1
11
45
1
3
3
3
1
5
Paso a paso (Iteracin 4)
Agregar elemento a S. Actualizar D S={1,3,2,5,4} V-S={ } D=[0,2,1,6,2]1 2 3 4 5
22
4 1
11
45
1
3
3
3
1
5
Final
|S| = |V| La mejor manera de llegar al vrtice u se encuentra en Du2
S={1,3,2,5,4} V-S={ } D=[0,2,1,6,2]1 2 3 4 5
2
4 1
11
45
1
3
3
3
1
5
Por qu funciona?
Supongamos delta(s,v) = Mejor manera de llegar de s a v Si Dijkstra funciona: Du=delta(s,u) para toda u en V
Demostracin por contradiccin
Suponga que u es el primer vrtice aadido a S tal que Dudelta(s,u)
Propiedades que tendra uu no puede ser s porque Ds = 0 Existe un camino de s a u, de lo contrario Ds = Si existe un camino, entonces debe existir el camino ms corto.
Suposicin principal
Sea s->(p1)->x->y->(p2)->u el camino ms corto de s a u.
Propiedades de x y y
x ya fue insertado en S Dx=delta(s,x) Posteriormente se actualiz el vrtice y, as que Dy=delta(s,y), pero aun no es insertado en S
Entonces
Puesto que y se encuentra antes que u: Dy=delta(s,y) Du delta(s,u) Pero partimos de que u esta siendo insertado en S, as que se debe cumplir que: D y Du
FinalmenteAs que:
Dy=delta(s,y) = Du=delta(s,u)
El Multiple Source ShortestPath Problem22 4 1 1
131
45
3
3
1
5
Cul es el problema?
Cul es la mejor manera de llegar al los puntos T (town o ciudad en naranja) a partir de cualquiera de los puntos S (fuente) ?
Consideraciones
Existe un conjunto de fuentes F En el camino ms corto para llegar a u, existe slo una fuente: f1->(p1)->f2->(p2)->v > f2->(p2)->v
Un problema ms real
Puntos Naranjas: Centros de Distribucin Puntos Grises: Ciudades De qu centro de distribucin es mejor partir a la ciudad X de tal manera de que gaste los menos recursos posibles? 22
4
11 3 1
1
45
3
3
5
Qu otro problema podemos resolver?
Puntos Naranjas: Centros de Distribucin Puntos Grises: Ciudades Quiero construir un nuevo Punto de Distribucin Cul es el mejor lugar para hacerlo? 22
4
11 1 3
1 3
4
3
1
5
Cmo lo resolvemos con Dijkstra?
Algoritmo glotn (greedy) Puntos de inicio Conjunto F Conjunto S Vector D
Condiciones iniciales
S=F={1,2} V-S={3,4,5} D=[0,0,1,4,3]1 2 3 4 5
22
4 1
11
45
1
3
3
3
1
5
Estado final
S={1,5,4,3,2} V-S={} D=[0,0,1,4,2]1 2 3 4 5
22
4 1
11
45
1
3
3
3
1
5
Conclusiones
Complejidad O(v2) pudindose reducir a O(nlogn) con Busqueda Binaria Procesa hasta 10,000 vrtices en 1 segundo
El Algoritmo de Dijkstra es rpido Demostramos que resuelve eficazmente nuestro problema