Scribd
Cargar
140 vistas5 páginas

Algoritmo de Dijkstra Explicado

El documento describe el algoritmo de Dijkstra para encontrar el camino más corto entre dos vértices en un grafo. Explica que el algoritmo realiza una búsqueda en anchura ponderada iterativamente seleccionando el vértice con menor peso desde el vértice inicial y actualizando las distancias de los vértices adyacentes hasta que no quedan vértices fuera del conjunto seleccionado.

Cargado por

Alexander Rodriguez
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
140 vistas5 páginas

Algoritmo de Dijkstra Explicado

El documento describe el algoritmo de Dijkstra para encontrar el camino más corto entre dos vértices en un grafo. Explica que el algoritmo realiza una búsqueda en anchura ponderada iterativamente seleccionando el vértice con menor peso desde el vértice inicial y actualizando las distancias de los vértices adyacentes hasta que no quedan vértices fuera del conjunto seleccionado.

Cargado por

Alexander Rodriguez
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

Caminos mas Cortos…

Dijkstra
2

Algoritmo de Dijkstra!
▫ La idea principal es realizar una búsqueda a lo ancho “ponderada”
empezando por el vértice inicial f.
▫ De manera iterativa se construye un conjunto de vértices
seleccionados S que se toman del conjunto de vértices candidatos
C según el menor peso (distancia) desde f.
▫ El algoritmo termina cuando no hay más vértices de G fuera del
conjunto formado.
▫ El paradigma usado corresponde al método voraz, en el que se trata
de optimizar una función sobre una colección de objetos (menor
peso).
▫ Se usa un vector d[v] para almacenar la distancia de v a f.
3

Algoritmo de Dijkstra!
▫ Cuando se añade un vértice al conjunto S, el valor de d[v] contiene la
distancia de f a v.
▫ Cuando se añade un nuevo vértice u al conjunto S, es necesario
comprobar si u es una mejor ruta para sus vértices adyacentes z que
están en el conjunto C.
▫ Para ello se actualiza d con la relajación de la arista (u, z):
▫
d[z] = min( d[z], d[u] + w[u, z] )
5

Demostración de Algoritmo
Con Pacman

También podría gustarte