No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Algoritmo de Dijkstra

35/40
Recursos

El algoritmo de Dijkstra va a buscar la ruta optima o de menor coste entre dos v茅rtices.

Los pasos de este algoritmo son los siguientes:

  1.    Asignar el valor infinito a cada nodo que no ha sido visitado.
    
  2.    Mantener un registro de los nodos visitados.
    
  3.    Calcular la distancia a cada nuevo nodo sumando la distancia anterior.
    
  4.    Si la nueva distancia que se calculo es menor que la anterior entonces reemplazar en el nodo, sino dejar la anterior.
    
  5.    Se finalizar谩 cuando se llega al nodo final.
    

Aportes 34

Preguntas 4

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

Platzi deber铆a poner la opci贸n de like a videos. Pues este v铆deo tendr铆a un like de mi parte.

Edsger Wyde Dijkstra(1930-2002). Estudio f铆sica te贸rica en la universidad de Leiden.
La soluci贸n del problema del camino mas corto fue una des sus contribuciones a la inform谩tica, tambi茅n conocido como el algoritmo de Dijkstra.

la respuesta del ejemplo es nodo: (a)-(b)-(d)-(f) = 11; pero falt贸 analizar otra ruta que tambi茅n nos da la ruta m谩s 贸ptima (a)-(e)-(d)-(f) =11. en ese orden de ideas, 驴cual seria el factor determinante para seleccionar alguna de las dos rutas?

Porque se habla de algoritmos y no se menciona en ningun momento, la complejidad computacional de esos algoritmos鈥 que es algo totalmente imprescindible a la hora de elegir usar un algoritmo u otro鈥

Algoritmo de dijkstra: Encuentra la ruta 贸ptima (menor coste) entre dos v茅rtices del 谩rbol de expansi贸n.
1: El v茅rtice inicial tendr谩 un valor de 0 y el resto de v茅rtices costar谩n infinito.
2: evaluamos las diferentes rutas, y si el costo de cada ruta es menor que el valor del v茅rtice al que estamos llegando entonces se actualiza con el menor valor.
3: se debe llevar un registro de los v茅rtices ya visitados
4: se hace una iteraci贸n con todas las rutas, hasta llegar al v茅rtice objetivo con el menor valor.

Este m茅todo es m谩s sencillo si usamos una tabla para desarrollar el algoritmo.

https://youtu.be/LLx0QVMZVkk

驴Porqu茅 el profesor les dice arboles y no grafos? A mi se me figura mas a un grafo a que un 谩rbol.

Algoritmo de Dijkstra
Permite hallar la ruta 贸ptima para conectar dos puntos.
Pasos:

  • Asignamos al nodo inicial un valor de 0 y a los otros nodos un valor de infinito
  • Calculamos el coste de cada ruta al nodo, si es menor que el valor anterior, entonces reemplazamos el valor del nodo y elegimos esa ruta
  • El algoritmo termina cuando hayamos llegado al nodo destino comparando las rutas posibles.

Excelente explicaci贸n, ahora entiendo un poco m谩s sobre el curso de algoritmos aunque no se trat贸 este tema en espec铆fico 馃槂

Es demasiado chimba jajajjjaaj, perdonen la expresi贸n pero lo amerita 

Tambi茅n podr铆a ser: a___7____e____2____d____2____f, que tambi茅n el menor coste es 11. Me ayudan si estoy bien o no?

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 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.

Si uno se est谩 devolviendo a cada nodo para actualizar el coste de la ruta 驴Cu谩l es la diferencia entre hacer esto o simplemente calcular el coste de todas las rutas posibles y tomar la menor?

Si una ruta es mas optima que otra respecto a un mismo punto se descarta la menos optima

  • 脡ste algoritmo puede ser usado para crear rutas de tr谩fico en una ciudad basados en intersecciones y distancias de las rutas. y Si hay data de tiempo tambi茅n puede ser un costo adicional al problema.

busca la ruta m谩s optima para conectar un punto inicial con un punto final.

Es probable que Waze y Google Maps utilicen este algoritmo similar para determinar el mejor camino para llegar de un punto a a a un punto F. Genial !! 馃槃

Notas de clase:
El algoritmo de Dijkstra va a buscar la ruta optima o de menor coste entre dos v茅rtices.
Edsger Wyde Dijkstra(1930-2002). Estudio f铆sica te贸rica en la universidad de Leiden.
La soluci贸n del problema del camino m谩s corto fue una de sus contribuciones a la inform谩tica, tambi茅n conocido como el algoritmo de Dijkstra.
Los pasos de este algoritmo son los siguientes:

  1. Asignar el valor infinito a cada nodo no visitado.
  2. Mantener un registro de los nodos visitados.
  3. Calcular la distancia a cada nuevo nodo sumando la distancia anterior.
  4. Si la nueva distancia calculada es menor que la anterior entonces reemplazar en el nodo, sino ignorarla.
  5. Visitamos el nodo de menor distancia y repetimos el paso 3.
  6. Se finalizar谩 cuando se llega al nodo final.
    Aporte extra:
    https://www.youtube.com/watch?v=LLx0QVMZVkk

En ingenier铆a de Transporte se le conoce como algoritmo de ruta m铆nima

El algoritmo de Dijkstra funciona as铆: 1. Asignar a cada nodo no visitado un valor infinito, 2. Luego asignar el valor de la ruta hacia el nodo, sumando las rutas anteriores a 茅l y guardar su valor. 3. Calcular la distancias a cada nuevo nodo sumando la distancia anterior. 4. Si la distancia nueva es calculada menor que la anterior, reemplazarla, sino ignorarlo. 5. El algoritmo finaliza cuando se llega al nodo final.

Lo que busca el algoritmo de Dijkstra, es encontrar el menor costo posible de un nodo ra铆z a un nodo final.

Se podria combinar el algoritmo de prim y el algoritmo de djkstra Para no tener que intentar con todas las aristas sino con solo aquellas que conosco de antemano que son la mejor opcion.

muy buen contenido鈥 el ejemplo se entendi贸 perfecto

Saludos a todos y a seguir estudiando! 馃槃

profesor: tambi茅n podr铆a ser (a -----e-------d------f)

buen maestro

Resumen del Algoritmo de dijkstra

Ejercicio demostrativo del Algoritmo de dijkstra

Me encant贸.

Muy bien explicado por el profesor! pero tambi茅n es bueno mencionar que abdf =11 y la ruta aedf = 11 dan igual鈥 por ende si fuera alguna decisi贸n log铆stica o empresarial ambas son validas

conocimiento nuevo.
excelente

Excelente