Estimados,
Deberíamos terminar hoy la entrega de grafos y comenzar con Dijkstra, así que no le dediquen más tiempo. La idea sería entregar este último el lunes 16/06 y dar por terminada esta parte del curso. No podemos estirarlo más.
Saludos,
Juan
No me queda claro como entraria el heap en la implementación de dijkstra (en la wiki dice comparar con y sin heap).
Alguna pista?
salute
matias
En cada paso al terminar de procesar el nodo actual, se pasa al nodo siguiente. Ese nodo siguiente se elige entre los vecinos del actual , como aquel que tiene la distancia mínima al nodo origen a. Dicho de otro modo, si mirás el pseudo código que hay en los slides, verás que dice: sea u=argmin(dist(v)).
Por tanto en cada paso necesitas saber el nodo con mínima distancia al origen (y además sacarlo) porque luego no lo vas a usar más.
Por lo tanto, si tenés N iteraciones y buscás un mínimo en cada iteración, la búsqueda del mínimo requiere hacerse con cuidado y de ahí la utilidad del heap?
Si no queda claro avisen que lo vemos con más detalle.
Saludos,
Juan
Dale, creo que entendi!
saludos
matias