Sesión 11_Mg Orleans Gálvez Tapia

Vista previa del material en texto

ANÁLISIS DE ALGORITMOS Y 
ESTRATEGIAS DE PROGRAMACIÓN
Docente: 
Mg. Gálvez Tapia Orleans Moisés
CIP. 171497
UNIDAD 1:
LA COMPLEJIDAD ALGORÍTMICA Y 
PRINCIPALES ESTRATEGIAS DE 
PROGRAMACIÓN
SEMANA 11: Camino más corto
(Algoritmo de Dijkstra)
¿Qué es una cola de 
prioridad?
SABERES PREVIOS
AGENDA:
1. Colas de prioridad en Python (heapq)
2. Uso de heappush(heap, item) y heappop(heap)
3. Camino más corto usando el algoritmo de Dijkstra
4. Pseudocódigo de algoritmo de Dijkstra
5. Prueba de escritorio de algoritmo de Dijkstra
6. Implementación en Python del algoritmo de Dijkstra
7. Trabajo grupal válido para la T2
8. Conclusiones
9. Referencias Bibliográficas
LOGRO DE LA SESIÓN
Al término de la clase, el estudiante implementa el algoritmo del camino 
más corto en Python, demostrando dominio del lenguaje y un lógica 
coherente.
COLA DE PRIORIDAD EN PYTHON
Salida:
(1, 'John') 
(2, 'Eric') 
(3, 'Andrew')
(4, 'Jean')
Se considera que el elemento con la clave más pequeña
tiene la prioridad más alta en colección.
COLA DE PRIORIDAD EN PYTHON
Se considera que el elemento con la clave más pequeña
tiene la prioridad más alta en colección.
heappush(heap, item)
Inserta el valor item en la cola de prioridad.
heappop(heap)
Desapila y retorna el elemento más pequeño
del heap, Para acceder al elemento más
pequeño sin necesidad de desapilar, usa
heap[0].
CAMINO MÁS CORTO USANDO DIJKSTRA
El algoritmo de Dijkstra es un algoritmo para encontrar los caminos más cortos entre los nodos de un grafo.
Para un nodo de origen dado en el grafo, el algoritmo encuentra el camino más corto entre ese nodo y todos los
demás nodos. Por ejemplo:
Vértices Costo mínimo Ruta
A —> B 4 A —> E —> B
A —> C 6 A —> E —> B —> C
A —> D 5 A —> E —> D
A —> E 3 A —> E
S es el conjunto de vértices cuyas distancias desde el
origen ya están calculadas (teniendo en cuenta que se
trata de la menor distancia).
CAMINO MÁS CORTO USANDO DIJKSTRA
CAMINO MÁS CORTO USANDO DIJKSTRA
CAMINO MÁS CORTO USANDO DIJKSTRA
El grafo que vamos a implementar en Python es el siguiente: 
CAMINO MÁS CORTO USANDO DIJKSTRA
Salida del programa en python:
CAMINO MÁS CORTO USANDO DIJKSTRA
PSEUDOCÓDIGO DEL ALGORITMO DE DIJKSTRA
1 método Dijkstra(Grafo,origen):
2 creamos una cola de prioridad Q
3 agregamos origen a la cola de prioridad Q
4 mientras Q no este vacío:
5 sacamos un elemento de la cola Q llamado u
6 si u ya fue visitado continuo sacando elementos de Q 
7 marcamos como visitado u
8 para cada vértice v adyacente a u en el Grafo:
9 sea w el peso entre vértices ( u , v ) 
10 si v no ah sido visitado:
11 Relajacion( u , v , w )
1 método Relajacion( actual , adyacente , peso ):
2 si distancia[ actual ] + peso < distancia[ adyacente ]
3 distancia[ adyacente ] = distancia[ actual ] + peso
4 agregamos adyacente a la cola de prioridad Q
distancia[ i ] como la distancia mas corta del vértice origen ingresado al vértice i.
PRUEBA DE ESCRITORIO DEL ALGORITMO DE DIJKSTRA
PRUEBA DE ESCRITORIO DEL ALGORITMO DE DIJKSTRA
[0] [1] [2] [3] [4]
-1 -1 -1 -1 -1previos
PRUEBA DE ESCRITORIO DEL ALGORITMO DE DIJKSTRA
[0] [1] [2] [3] [4]
-1 -1 0 4 -1 4 1 -1 4 -1 0
[0] [1] [2] [3] [4]
-1 4 1 4 0
previos
previos
Camino (0 —> 1): Mínimo costo = 4, Ruta = [0, 4, 1]
Camino (0 —> 2): Mínimo costo = 6, Ruta = [0, 4, 1, 2]
Camino (0 —> 3): Mínimo costo = 5, Ruta = [0, 4, 3] 
Camino (0 —> 4): Mínimo costo = 3, Ruta = [0, 4] 
PRUEBA DE ESCRITORIO DEL ALGORITMO DE DIJKSTRA
[0] [1] [2] [3] [4]
0 4 6 5 3distancia
Camino (0 —> 1): Mínimo costo = 4, Ruta = [0, 4, 1]
Camino (0 —> 2): Mínimo costo = 6, Ruta = [0, 4, 1, 2]
Camino (0 —> 3): Mínimo costo = 5, Ruta = [0, 4, 3] 
Camino (0 —> 4): Mínimo costo = 3, Ruta = [0, 4] 
PRUEBA DE ESCRITORIO DEL ALGORITMO DE DIJKSTRA
EXPLICACIÓN DEL FUNCIONAMIENTO DEL PROGRAMA
class Nodo:
def __init__(self, vertice, peso=0):
self.vertice = vertice
self.peso = peso
def __lt__(self, objeto2):
return self.peso < objeto2.peso
vertice
peso
<
Nodo
origen destino peso
0 1 10
0 4 3
1 2 2
1 4 4
2 3 9
3 2 7
4 1 1
4 2 8
4 3 2
aristas
EXPLICACIÓN DEL FUNCIONAMIENTO DEL PROGRAMA
aristas = [(0, 1, 10), (0, 4, 3), 
(1, 2, 2), (1, 4, 4), 
(2, 3, 9), 
(3, 2, 7),
(4, 1, 1), (4, 2, 8), (4, 3, 2)]
n = 5
origen destino peso
0 1 10
0 4 3
1 2 2
1 4 4
2 3 9
3 2 7
4 1 1
4 2 8
4 3 2
aristas
EXPLICACIÓN DEL FUNCIONAMIENTO DEL PROGRAMA
class Grafo:
def __init__(self, aristas, n):
self.lista_adyacencia = [[] for _ in range(n)]
for (origen, destino, peso) in aristas:
self.lista_adyacencia[origen].append((destino, peso))
[ ]
[ ]
[ ]
[ ]
[ ]
Lista de Adyacencia
[0] (1 , 10)
[0] (4 , 3)
[1] (2 , 2)
[1] (4 , 4)
[2] (3 , 9)
[3] (2 , 7)
[4] (1 , 1)
[4] (2 , 8)
[4] (3 , 2)
for (origen, destino, peso) in aristas:
[0] [ (1,10) , (4,3) ]
[1] [ (2,2) , (4,4) ]
[2] [ (3,9) ]
[3] [ (2,7) ]
[4] [ (1,1) , (2,8) , (3,2) ]
Lista de Adyacencia
EXPLICACIÓN DEL FUNCIONAMIENTO DEL PROGRAMA
[0, ∞, ∞, ∞, ∞]
Consideramos: sys.maxsize = 9223372036854775807 = ∞
def camino_mas_corto(grafo, origen, n):
pq = []
heappush(pq, Nodo(origen))
distancia = [sys.maxsize] * n
distancia[origen] = 0
visitado = [False] * n
visitado[origen] = True
previos = [-1] * n
while pq:
…
ruta = []
for i in range(n):
…
[True, False, False, False, False]
[-1, -1, -1, -1, -1]
[ 0 ]
EXPLICACIÓN DEL FUNCIONAMIENTO DEL PROGRAMA
# pq = [ ]
# u = 0
CAMINO MAS CORTO, IMPLEMENTACIÓN EN PYTHON
TRABAJO EN EQUIPOS
1. Realizar la prueba de escritorio del algoritmo de Dijkstra para todos los nodos que faltan:
TRABAJO EN EQUIPOS
1. Realizar la prueba de escritorio del algoritmo de Dijkstra para todos los nodos que faltan:
TRABAJO EN EQUIPOS
2. Realizar una prueba de escritorio (en Excel) del algoritmo de ordenamiento quicksort:
[0] [1] [2] [3] [4] [5]
10 40 7 9 15 27
TRABAJO EN EQUIPOS
3. Realizar una prueba de escritorio (en Excel) del algoritmo de búsqueda binaria recursiva:
[0] [1] [2] [3] [4] [5]
7 9 10 15 27 40 Dato buscado
TRABAJO EN EQUIPOS
4. Realizar una prueba de escritorio (en Excel) del algoritmo de las torres de hanoi:
Considerar 4 discos
CONCLUSIONES
1. Las colas de prioridad son estructuras de datos en las que cada dato/valor de la cola tiene una
determinada prioridad
o Un elemento con prioridad alta se elimina de la cola antes que un elemento con prioridad baja.
o Si dos elementos tienen la misma prioridad, se sirven según su orden en la cola.
2. El algoritmo de Dijkstra es un algoritmo iterativo que nos proporciona la ruta más corta desde un nodo
inicial particular a todos los otros nodos en un grafo.
REFERENCIAS BIBLIOGRÁFICAS
REFERENCIA ENLACE 
Una introducción a las matemáticas para el 
análisis y diseño de algoritmos 
https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/35059
Manual de algorítmica: recursividad, complejidad y 
diseño de algoritmos 
https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/56561
Introducción práctica a la programación con 
Python 
https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/124259
Criptografía sin secretos con Python https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/106497
ACM UVA Online http://uva.onlinejudge.org/
ACM ICPC Competition https://icpc.global/compete/preparation
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/35059
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/35059
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/56561
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/56561
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/124259
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/124259
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/106497https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/106497
http://uva.onlinejudge.org/
https://icpc.global/compete/preparation
	Diapositiva 1
	Diapositiva 2
	Diapositiva 3: UNIDAD 1: LA COMPLEJIDAD ALGORÍTMICA Y PRINCIPALES ESTRATEGIAS DE PROGRAMACIÓN
	Diapositiva 4
	Diapositiva 5
	Diapositiva 6
	Diapositiva 7
	Diapositiva 8
	Diapositiva 9
	Diapositiva 10
	Diapositiva 11
	Diapositiva 12
	Diapositiva 13
	Diapositiva 14
	Diapositiva 15
	Diapositiva 16
	Diapositiva 17
	Diapositiva 18
	Diapositiva 19
	Diapositiva 20
	Diapositiva 21
	Diapositiva 22
	Diapositiva 23
	Diapositiva 24
	Diapositiva 25
	Diapositiva 26
	Diapositiva 27
	Diapositiva 28
	Diapositiva 29
	Diapositiva 30
	Diapositiva 31
	Diapositiva 32
	Diapositiva 33
	Diapositiva 34