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

CAMINO MAS CORTO:

No description
by

seus mayhua ayala

on 26 November 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of CAMINO MAS CORTO:

CAMINO MAS CORTO:
ALGORITMO DE DIJKSTRA - ETIQUETADO

ejemplo 1
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

COMO SE TRABAJA EL GRAFO
DESCRIPCION
DEFINICION
COMO PRIMER VALOR, PONEMOS LA DISTANCIA ACUMULADA (DESDE EL INICIO HASTA ESTE NODO)

SE AGREGA EL NUMERO DE INTERACCIONES (LA CANTIDAD DE OPERACIONES REALIZADAS)

SE AGREGA EL NODO PRECESESOR (ES EL NODO ANTERIOR AL NODO QUE ESTAMOS ETIQUETANDO)
ETIQUETADO
Primero marcamos todos los vértices como no utilizados. El algoritmo parte de un vértice origen que será ingresado, a partir de ese vértices evaluaremos sus adyacentes, como dijkstra usa una técnica greedy – La técnica greedy utiliza el principio de que para que un camino sea óptimo

todos los caminos que contiene también deben ser óptimos- entre todos los vértices adyacentes, buscamos el que esté más cerca de nuestro punto origen, lo tomamos como punto intermedio y vemos si podemos llegar más rápido a través de este vértice a los demás. Después escogemos al siguiente más cercano (con las distancias ya actualizadas) y repetimos el proceso. Esto lo hacemos hasta que el vértice no utilizado más cercano sea nuestro destino. Al proceso de actualizar las distancias tomando como punto intermedio al nuevo vértice se le conoce como relajación (relaxation).
Dijkstra es muy similar a BFS,(usa una Cola para el recorrido) para el caso de Dijkstra usaremos una Cola de Prioridad o Heap, este Heap debe tener la propiedad de Min-Heap es decir cada vez que extraiga un elemento del Heap me debe devolver el de menor valor, en nuestro caso dicho valor será el peso acumulado en los nodos
EJEMPLO 1
Se tiene las siguientes zonas: A,B,C,D,E,F,G y H. Como se muestra en el grafico las distancias están expresadas en kilómetros. Hallar la ruta mas corta con respecto a la zona A
PASO 1
Se escoge el nodo A y se etiqueta como se muestra en el diagrama
PASO 2
Se procede a etiquetar a los nodos adyacentes C y B respectivamente. Después de ello se aculan las distancias y se escoge quien posea menor distancia aculada.

PASO 3
Se procede a etiquetar los siguientes nodos adyacentes D y F, es asi que en este caso se observan que hay dos nodos que poseen distancia aculada cortas, se escoge cualquiera aleatoriamente, en este caso se elegirá D
PASO 4
Se etiquetan los nodos adyacentes y se conserva la etiqueta que tiene menor acumulación de distancia, se procede después de ello a tomar el nodo con menor distancia acumulada
PASO 5
Des procede con las interacciones y se observa que H tiene dos soluciones con igual adulación de distancia. Ello quiere decir que para H hay dos posibles rutas con distancia mínima
EJEMPLO 2
PASO 1
Partimos de A. Observamos que A está conectado a dos vértices: B y C. El vértice B está conectado a A con un camino cuyo coste es 4, mientras que el vértice C está conectado a A con un camino cuyo vértice es 2. Así que optamos por recorrer este último camino hasta llegar a C.
PASO 2
Con el nuevo vértice C aparecen nuevos candidatos en forma de nodos para seguir acercándonos a F. Valoramos las distancias que hay que recorrer para llegar a ellos. Observamos que de C a D tenemos un camino de 8 y de C a E un camino de 10, mientras que de C a B un camino de 1. Por lo tanto, optamos por recorrer este último tramo. Sumamos este 1 a la distancia recorrida anteriormente, que era 2.
PASO 3
PASO 4
Al llegar a D, visualizamos en la distancia el nodo objetivo F, pero también tenemos acceso al nodo E que veíamos desde C. Éste se encuentra a una distancia de 2, mientras que F (desde D que es donde estamos) está a 6. Recorremos por tanto el camino que nos lleva de D a E, y lo sumamos a lo que teníamos antes.

PASO 5
Ya casi hemos llegado. Desde E podemos ver F a una distancia de 3. Debemos recorrer esta distancia para llegar a nuestro nodo objetivo, y lo sumamos a lo recorrido tota
Calcularemos el camino más corto desde el nodo A hasta el nodo F utilizando el algoritmo de Dijkstra

Llegamos al vértice B. Aparece un nuevo vértice candidato: D, cuyo recorrido hasta él es de 5. Aún con todo, no tenemos otro remedio que tomar ese camino, puesto que no podemos volver atrás.Sumamos este camino al que ya hemos recorrido
CONSIDERACIONES

a) Si los pesos de mis aristas son de valor 1, entonces bastará con usar el algoritmo de BFS
b) Si los pesos de mis aristas son negativos no puedo usar el algoritmo de dijsktra, para pesos negativos tenemos otro algoritmo llamado Algoritmo de Bellmand-Ford

El algoritmo de Dijkstra, 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 los vértices en un grafo con pesos en cada arista.
 

UNIVERSIDAD NACIONAL DE SAN AGUSTIN FACULTAD DE PRODUCCION Y SERVICIOS
ESCUELA PROFECIONAL DE INGENIERIA INDUSTRIAL
DOCENTE: ING. EFRAIN MURILLO

INTEGRANTES
MAYHUA AYALA SEUS LUIS
CANALES RAMOS JOHANN
MIRANDA CALLO PERCY
QUISPE TAPIA NIMAI
VALIDIVIA BALDARRAGO KARLA
SALAS MANZANO ANGIE
CCORIMANYA TIMOTEO JUANA
ARAPA CHAMBI ANDRE
AREQU
IPA-P
ERU
Full transcript