Algoritmo de Dijkstra

48 %
52 %
Information about Algoritmo de Dijkstra

Published on June 5, 2007

Author: joemmanuel

Source: slideshare.net

Description

Analisis del Algoritmo de Dijkstra

Caminos más cortos a partir de múltiples fuentes en un grafo Joemmanuel Ponce Galindo

¿Qué es un grafo?

Un grafo es… Una pareja ordenada G(V,E) con las siguientes características: V es un conjunto de vértices E es un conjunto de parejas de distintos vértices, entre los cuales se trazan líneas (aristas)

Una pareja ordenada G(V,E) con las siguientes características:

V es un conjunto de vértices

E es un conjunto de parejas de distintos vértices, entre los cuales se trazan líneas (aristas)

Grafos ponderados 1 2 4 3 5 2 4 1 1 5 3 1 1 3

Entonces l(a) = peso de la arista ‘a’ l(x,y) = peso de la arista de x a y

l(a) = peso de la arista ‘a’

l(x,y) = peso de la arista de x a y

¿Y qué podemos modelar? 1 0 3 5 6 4 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 5 3 8 6 1 2 4 3 5 1 1 1 1 1 2 4 2 3 3 2 1 3

Problema de la ruta mínima (Single Source) ¿Cómo llego del punto 1 a 4 de la manera más corta posible? 1 2 4 3 5 2 4 1 1 5 3 1 1 3

¿Cómo se resuelve? Existen algoritmos genéricos para ello: Dijkstra Algorithm Floyd Algorithm Bellman-Ford Algorithm

Existen algoritmos genéricos para ello:

Dijkstra Algorithm

Floyd Algorithm

Bellman-Ford Algorithm

Algoritmo de Dijkstra Algoritmo glotón (greedy) Punto de inicio s Conjunto S Vector D 1 2 4 3 5 2 4 1 1 5 3 1 1 3

Algoritmo glotón (greedy)

Punto de inicio s

Conjunto S

Vector D

Condiciones iniciales S={ 1 } V-S={ 2,3,4,5 } D=[ 0 , 2,1, ∞,3 ] 1 2 3 4 5 1 2 4 3 5 2 4 1 1 5 3 1 1 3

S={ 1 }

V-S={ 2,3,4,5 }

D=[ 0 , 2,1, ∞,3 ]

1 2 3 4 5

El algoritmo Aumentar S agregando el elemento v en V-S tal que D v sea el mínimo de ese conjunto. Actualizar los valores de D i para todos los elementos i existentes en V-S . D i =mínimo( D i , D v +f(v, i) ) Terminar cuando |S|=|V|

Aumentar S agregando el elemento v en V-S tal que D v sea el mínimo de ese conjunto.

Actualizar los valores de D i para todos los elementos i existentes en V-S .

D i =mínimo( D i , D v +f(v, i) )

Terminar cuando |S|=|V|

Paso a paso (Iteración 1) Buscar mínimo D i en V-S S={ 1 } V-S={ 2,3,4,5 } D=[ 0 , 2,1, ∞,3 ] 1 2 3 4 5 1 2 4 3 5 2 4 1 1 5 3 1 1 3

Buscar mínimo D i en V-S

S={ 1 }

V-S={ 2,3,4,5 }

D=[ 0 , 2,1, ∞,3 ]

1 2 3 4 5

Paso a paso (Iteración 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 1 2 4 3 5 2 4 1 1 5 3 1 1 3

Agregar elemento a S . Actualizar D

S={ 1,3 }

V-S={ 2,4,5 }

D=[ 0 , 2 , 1 , ∞,3 ]

1 2 3 4 5

Paso a paso (Iteración 2) Buscar mínimo D i en V-S S={ 1,3 } V-S={ 2,4,5 } D=[ 0 , 2 , 1 , ∞,2 ] 1 2 3 4 5 1 2 4 3 5 2 4 1 1 5 3 1 1 3

Buscar mínimo D i en V-S

S={ 1,3 }

V-S={ 2,4,5 }

D=[ 0 , 2 , 1 , ∞,2 ]

1 2 3 4 5

Paso a paso (Iteración 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 1 2 4 3 5 2 4 1 1 5 3 1 1 3

Agregar elemento a S . Actualizar D

S={ 1,3,2 }

V-S={ 4,5 }

D=[ 0 , 2 , 1 , ∞ , 2 ]

1 2 3 4 5

Paso a paso (Iteración 3) Buscar mínimo D i en V-S S={ 1,3,2 } V-S={ 4,5 } D=[ 0 , 2 , 1 , 6 , 2 ] 1 2 3 4 5 1 2 4 3 5 2 4 1 1 5 3 1 1 3

Buscar mínimo D i en V-S

S={ 1,3,2 }

V-S={ 4,5 }

D=[ 0 , 2 , 1 , 6 , 2 ]

1 2 3 4 5

Paso a paso (Iteración 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 1 2 4 3 5 2 4 1 1 5 3 1 1 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

Paso a paso (Iteración 4) Buscar mínimo D i en V-S S={ 1,3,2,5 } V-S={ 4 } D=[ 0 , 2 , 1 , 6 , 2 ] 1 2 3 4 5 1 2 4 3 5 2 4 1 1 5 3 1 1 3

Buscar mínimo D i en V-S

S={ 1,3,2,5 }

V-S={ 4 }

D=[ 0 , 2 , 1 , 6 , 2 ]

1 2 3 4 5

Paso a paso (Iteración 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 1 2 4 3 5 2 4 1 1 5 3 1 1 3

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

Final |S| = |V| La mejor manera de llegar al vértice u se encuentra en D u S={ 1,3,2,5,4 } V-S={ } D=[ 0 , 2 , 1 , 6 , 2 ] 1 2 3 4 5 1 2 4 3 5 2 4 1 1 5 3 1 1 3

|S| = |V|

La mejor manera de llegar al vértice u se encuentra en D u

S={ 1,3,2,5,4 }

V-S={ }

D=[ 0 , 2 , 1 , 6 , 2 ]

1 2 3 4 5

¿Por qué funciona? Supongamos delta(s,v) = Mejor manera de llegar de s a v Si Dijkstra funciona: D u = delta(s,u) para toda u en V

Supongamos delta(s,v) = Mejor manera de llegar de s a v

Si Dijkstra funciona:

D u = delta(s,u) para toda u en V

Demostración por contradicción Suponga que u es el primer vértice añadido a S tal que D u ≠ delta(s,u)

Suponga que u es el primer vértice añadido a S tal que D u ≠ delta(s,u)

Propiedades que tendría u u no puede ser s porque D s = 0 Existe un camino de s a u , de lo contrario D s = ∞ Si existe un camino, entonces debe existir el camino más corto.

u no puede ser s porque D s = 0

Existe un camino de s a u , de lo contrario

D s = ∞

Si existe un camino, entonces debe existir el camino más corto.

Suposición principal Sea s->(p1)->x->y->(p2)->u el camino más corto de s a u .

Sea s->(p1)->x->y->(p2)->u el camino más corto de s a u .

Propiedades de x y y x ya fue insertado en S D x =delta(s,x) Posteriormente se actualizó el vértice y , así que D y =delta(s,y) , pero aun no es insertado en S

x ya fue insertado en S

D x =delta(s,x)

Posteriormente se actualizó el vértice y , así que D y =delta(s,y) , pero aun no es insertado en S

Entonces Puesto que y se encuentra antes que u: D y =delta(s,y) ≤ D u ≤ delta(s,u) Pero partimos de que u esta siendo insertado en S , así que se debe cumplir que: D y ≥ D u

Puesto que y se encuentra antes que u:

D y =delta(s,y) ≤ D u ≤ delta(s,u)

Pero partimos de que u esta siendo insertado en S , así que se debe cumplir que:

D y ≥ D u

Finalmente Así que: D y =delta(s,y) = D u =delta(s,u)

Así que:

D y =delta(s,y) = D u =delta(s,u)

El Multiple Source Shortest-Path Problem 1 2 4 3 5 2 4 1 1 5 3 1 1 3

¿Cuál es el problema? ¿Cuál es la mejor manera de llegar al los puntos T (town o ciudad en naranja) a partir de cualquiera de los puntos S (fuente) ?

¿Cuál 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 más corto para llegar a u , existe sólo una fuente: f 1 ->(p1)-> f 2 ->(p2)->v > f 2 ->(p2)->v

Existe un conjunto de fuentes F

En el camino más corto para llegar a u , existe sólo una fuente:

f 1 ->(p1)-> f 2 ->(p2)->v > f 2 ->(p2)->v

Un problema más real Puntos Naranjas: Centros de Distribución Puntos Grises: Ciudades ¿De qué centro de distribución es mejor partir a la ciudad X de tal manera de que gaste los menos recursos posibles? 5 1 2 4 3 5 2 4 1 1 3 1 1 3

Puntos Naranjas: Centros de Distribución

Puntos Grises: Ciudades

¿De qué centro de distribución es mejor partir a la ciudad X de tal manera de que gaste los menos recursos posibles?

¿Qué otro problema podemos resolver? Puntos Naranjas: Centros de Distribución Puntos Grises: Ciudades Quiero construir un nuevo Punto de Distribución ¿Cuál es el mejor lugar para hacerlo? 1 2 4 3 5 2 4 1 1 3 1 1 3

Puntos Naranjas: Centros de Distribución

Puntos Grises: Ciudades

Quiero construir un nuevo Punto de Distribución ¿Cuál es el mejor lugar para hacerlo?

¿Cómo lo resolvemos con Dijkstra? Algoritmo glotón (greedy) Puntos de inicio Conjunto F Conjunto S Vector D

Algoritmo glotón (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 1 2 4 3 5 2 4 1 1 5 3 1 1 3

S= F ={ 1,2 }

V-S={ 3,4,5 }

D=[ 0 , 0 ,1, 4,3 ]

1 2 3 4 5

Estado final S={ 1,5,4,3,2 } V-S={} D=[ 0 , 0,1, 4,2 ] 1 2 3 4 5 1 2 4 3 5 2 4 1 1 5 3 1 1 3

S={ 1,5,4,3,2 }

V-S={}

D=[ 0 , 0,1, 4,2 ]

1 2 3 4 5

Conclusiones Complejidad O(v 2 ) pudiéndose reducir a O(nlogn) con Busqueda Binaria Procesa hasta 10,000 vértices en 1 segundo El Algoritmo de Dijkstra es rápido Demostramos que resuelve eficazmente nuestro problema

Complejidad O(v 2 ) pudiéndose reducir a O(nlogn) con Busqueda Binaria

Procesa hasta 10,000 vértices en 1 segundo

El Algoritmo de Dijkstra es rápido

Demostramos que resuelve eficazmente nuestro problema

Add a comment

Related presentations

Related pages

Dijkstra-Algorithmus – Wikipedia

Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) ist ein Algorithmus aus der Klasse der Greedy-Algorithmen und löst das Problem der ...
Read more

Dijkstra's algorithm - Wikipedia

Dijkstra's algorithm to find the shortest path between a and b. It picks the unvisited vertex with the lowest distance, calculates the distance through it ...
Read more

DIJKSTRA’S ALGORITHM - MIT Mathematics

Dijkstra’s Algorithm ! Solution to the single-source shortest path problem in graph theory ! Both directed and undirected graphs ! All edges must have ...
Read more

Dijkstra's shortest path algorithm in Java - Tutorial

Dijkstra’s Shortest Path Algorithm in Java. Dijkstra’s Algorithms describes how to find the shortest path from one node to another node in a directed ...
Read more

Dijkstra Algorithm - CodeProject

Hi, I implemented another Dijkstra Algorithm by using Java. However, I feel my program which i wrote is not good enough if there are two way that can go to ...
Read more

Dijkstra's algorithm - Rosetta Code

Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the ...
Read more

Der Dijkstra-Algorithmus - YouTube

Standard YouTube License; Loading ... 02 Algoritmo de DIJKSTRA - Duration: 4:51. Studios CAT 114,136 views. 4:51 Loading more suggestions ...
Read more

Shortest Path Problem: Dijkstra's Algorithm

JavaScript demos of Dijkstra's algorithm to solve shortest path problems.
Read more

Graphs: Dijkstra's Algorithm - YouTube

How to find least-cost paths in a graph using Dijkstra's Algorithm. This video is distributed under the Creative Commons Attribution 2.5 Canada ...
Read more

Dijkstra's Shortest Path Algorithm - University of Toronto

Dijkstra's Shortest Path Algorithm Here's an excellent applet by Carla Laffra of Pace University. Choose items from the menu in the upper-left corner.
Read more