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 de Dijkstra. También llamado algoritmo de caminos

No description
by

Omar Guzman

on 15 November 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Algoritmo de Dijkstra. También llamado algoritmo de caminos

A
B
D
E
C
H
G
F
También llamado algoritmo de caminos mínimos, 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. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.
Algoritmo de Dijkstra
APLICACIÓN DE LA TEORÍA DE GRAFOS Y EL ALGORITMO DE DIJKSTRA PARA DETERMINAR LAS DISTANCIAS Y LAS RUTAS MÁS CORTAS EN UNA CIUDAD

JORGE HERNÁN RESTREPO C, JOHN JAIRO SÁNCHEZ C.

Municipio de Santa Rosa de Cabal en Risaralda - Colombia
APLICACIONES DEL ALGORITMO DE DIJKSTRA
- Redes de computadores.
-Enrutamiento de aviones y tráfico aéreo
- tratamiento de imágenes médicas.
- Encaminamiento de paquetes en los router.
- En los motores de búsqueda de los navegadores.
- GPS
FUNCIONAMIENTO ALGORITMO DE DIJKSTRA
REFERENCIAS
CONCLUSIONES
Algoritmo de Dijkstra
- El algoritmo de Dijkstra analiza cada métrica para elegir la mejor ruta entre un punto inicial y uno final.

- Aplicado en una red, hace que todos los router conozcan la topología de la red.

- Este algoritmo no funciona adecuadamente con valores negativos.

DATOS IMPORTANTES
- El algoritmo Dijkstra dio origen al protocolo de enrutamiento OSPF.

- Es el algoritmo más usado para hallar el camino más corto.

El algoritmo de Dijkstra es de complejidad cuadrática O(n^2), (Operaciones sumas y comparaciones) ya que realiza la búsqueda desde su posición origen hasta el resto de los nodos.
http://www.cisco.com/c/en/us/support/docs/ip/open-shortest-path-first-ospf/7039-1.html

http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra

http://euler.uc3m.es/matematicadiscreta/GrafoMin/index.html
¿QUE ES UN GRAFO?
Para las ciencias de la computación, las matemáticas y para el protocolo de Dijkstra, un grafo es una representación gráfica de diversos puntos que se conocen como nodos o vértices, los cuales se encuentran unidos a través de líneas que reciben el nombre de aristas.
¿QUE ES UN GRAFO PONDERADO?
Es un grafo con valores en sus aristas.
Full transcript