Platzi debería poner la opción de like a videos. Pues este vídeo tendría un like de mi parte.
Introducción al curso
Todo lo que aprenderás sobre matemáticas discretas
Lógica
Introducción a la lógica
Conectores lógicos
Tablas de verdad
Ejemplo de tabla de verdad
Más ejemplos de tabla de verdad
Circuitos lógicos
Ejemplo de circuitos lógicos
Ejercicios - Lógica
Teoría de conjuntos
Introducción a los conjuntos
Operaciones entre conjuntos
Representación gráfica de conjuntos
Ley de Morgan: Unión de conjuntos
Ley de Morgan: Intersección de conjuntos
Ejercicio de Conjuntos
Ejercicios - Teoría de Conjuntos
Teoría de grafos
Teoría de grafos
Grados, caminos, cadenas y ciclos
Caminos y ciclos eulerianos
Caminos y ciclos hamiltonianos
Matriz de adyacencia
Matriz de incidencia
Ejercicio con matrices
Ejercicios - Teoría de gráficas
Árboles
Introducción a los árboles
Árboles
Sub árboles, vértices, y notación
Árbol de expansión mínimo
Árbol binario
Recorrido de árboles
Expresiones aritméticas
Ejercicio: Llevando una expresión aritmética a árbol
Ejercicios - Árboles
Algoritmos
Algoritmo de Prim
Algoritmo de Dijkstra
Algoritmo de Kruskal
Algoritmo de Fleury
Algoritmo de flujo máximo
Ejercicios - Algoritmos
Conclusiones
Conclusiones del curso
No tienes acceso a esta clase
¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera
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:
Asignar el valor infinito a cada nodo que no ha sido visitado.
Mantener un registro de los nodos visitados.
Calcular la distancia a cada nuevo nodo sumando la distancia anterior.
Si la nueva distancia que se calculo es menor que la anterior entonces reemplazar en el nodo, sino dejar la anterior.
Se finalizará cuando se llega al nodo final.
Aportes 34
Preguntas 4
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.
¿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:
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
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:
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
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?
o inicia sesión.