Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Algoritmo Dijkstra - Analisis de Algoritmos

Presentacion Usada para el ramo Analisis de Algoritmos - INACAP 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Algoritmo Dijkstra - Analisis de Algoritmos

Algoritmo de Dijkstra
Ejemplo:
Donde se utiliza?
Pseudocódigo del Algoritmo
Video Ejemplo
Algoritmo de Dijkstra
Vicente Alarcón Arias
Es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene.

Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.
Este algoritmo se usa bastante en redes de computadores, los nodos corresponden a routers y las aristas entre ellos las conexiones, a cada conexión se le asigna un costo (distancia) y de esta manera algunos protocolos de enrutamiento usan el algoritmo de Dijkstra para encontrar la mejor ruta entre nodos.
El costo de la ruta más corta para que R2 envíe paquetes a la LAN conectada a R3 es 27. Aquí se observa que este costo no es 27 para que todos los routers alcancen la LAN conectada a R3. Cada router determina su propio costo hacia cada destino en la topología.
DIJKSTRA (Grafo G, nodo_fuente s)
// Inicializamos todos los nodos del grafo-. La distancia de cada
nodo es infinita.
// Los padres son null
para u ∈ V[G] hacer
distancia[u] = INFINITO
padre[u] = NULL
distancia[s] = 0
adicionar (cola, (s,distancia[s]))
mientras que cola no es vacía hacer
// Se extrae el nodo que tiene distancia minima, conservando
// la condición de cola de prioridad
u = extraer_minimo(cola)
para todos v ∈ adyacencia[u] hacer
si distancia[v] > distancia[u] + peso (u, v) hacer
distancia[v] = distancia[u] + peso (u, v)
padre[v] = u
adicionar(cola,(v,distancia[v]))
Otras aplicaciones:
- Enrutamiento de aviones y tráfico aéreo: Consiste en un agente de solicitudes de viaje software para hacer un programa de vuelos para los clientes. El agente tiene acceso a una base de datos con todos los aeropuertos y los vuelos como el número de vuelo, el aeropuerto de origen y destino y los horarios de salida y de llegada. La aplicación se usa para determinar la hora de llegada más temprana para el destino dado un aeropuerto de origen y hora de inicio.

- Tratamiento de imágenes médicas.
Problemas reales en los que la solución es Dijkstra
-Llegar a desde un punto de una ciudad hasta otro por el camino más rápido

-Cómo rodear una montaña por el camino más corto

-Conocer el camino más rápido que sigue la información a través de las neuronas.
Complejidad
El Algoritmo de Dijkstra realiza O(n^2) operaciones (sumas y comparaciones) para determinar la longitud del camino más corto entre dos vértices de un grafo ponderado simple, conexo y no dirigido con n vértices, esto sin utilizar cola de prioridad.

O((|E|+|V|) log |V|) utilizando cola de prioridad (por ejemplo un montículo).
OpenStreetMap puede considerarse la “Wikipedia de los Mapas”. Es un proyecto para proveer datos geográficos gratuitos y de libre disposición para todo el mundo. Fue concebido en 2004 por Steve Coast para hacer frente al alto costo de los datos geográficos de Gran Bretaña, que en ese momento estaban monopolizados por el Ordnance Survey, un ente gubernamental.
OpenStreetMap permite generar mapas de lugares que hasta ahora no estaban disponibles, o modificar y mejorar los existentes, y dejarlos como dominio público.
Comparación
http://www.openstreetmap.cl/comparacion/
Conclusión
El algoritmo nos ofrece la solución de determinar
el camino mas corto, por lo tanto el que mas nos
conviene en un trayecto.
Al investigar los distintos contenidos, aplicaciones
vídeos y como funcionaba este algoritmo, uno se da
cuenta de lo importante que puede llegar a ser
si se le da un uso apropiado y se incorpora en software modernos.
¿Qué es Waze?
Es una aplicación gratuita de navegación GPS gratuita que incorpora características de navegación, desarrollada por Waze Mobile para teléfonos inteligentes. Actualmente soporta iOS, Android, Windows Mobile, Symbian, y BlackBerry.

Waze difiere del software GPS tradicional en que es una aplicación mantenida por la comunidad de usuarios y que aprende de las rutas recorridas por sus usuarios para proveer información de enrutamiento y actualizaciones de tráfico en tiempo real. Es un producto gratuito para utilizar donde las personas pueden reportar accidentes, congestiones de tráfico, controles de velocidad, puntos de interés entre otros. El programa requiere una conexión de datos en el dispositivo móvil.
Video Tutorial
B.iCycle
Nos muestra las rutas que vamos a seguir y hemos seguido, las distancias recorridas y la velocidad en intervalos, para saber en qué momento hemos apretado más el pedal. Nos permite saber las calorías que estamos quemando, la altitud a la que estamos en un momento determinado.
Disponible en Android y Windows Phone
Compatibilidad con Google Earth
Full transcript