Introducción al curso

1

Matemáticas Discretas: Lógica, Conjuntos y Teoría de Gráficas

Lógica

2

Lógica Proposicional: Conceptos y Aplicaciones Básicas

3

Tablas de verdad y conectores lógicos: conjunción, disyunción y más

4

Construcción de Tablas de Verdad para Proposiciones Compuestas

5

Construcción de Tablas de Verdad para Proposiciones Lógicas

6

Tablas de Verdad y Análisis de Proposiciones Lógicas

7

Circuitos Lógicos: Representación y Función en Electrónica

8

Circuitos Lógicos para Proposiciones Compuestas

9

Tablas y Circuitos Lógicos: Ejercicios Prácticos

Teoría de conjuntos

10

Conjuntos: Definición, Pertenencia y Representación Matemática

11

Conjuntos: Nulo, Unitario y Universal y Operaciones Básicas

12

Representación Gráfica de Operaciones entre Conjuntos

13

Propiedades de los Conjuntos: Leyes de De Morgan y Representación Gráfica

14

Representación gráfica de las leyes de De Morgan

15

Operaciones y Propiedades de Conjuntos: Ejercicio Práctico Resuelto

16

Operaciones Básicas con Conjuntos y Problemas de Conjuntos

Teoría de grafos

17

Teoría de Gráficas: Conceptos y Aplicaciones Prácticas

18

Grado de Vértices y Conexiones en Gráficas Simples

19

Caminos y ciclos eulerianos en grafos: teoría y aplicación

20

Caminos y Ciclos Hamiltonianos en Grafos

21

Construcción de Matrices de Adyacencia para Representar Grafos

22

Representación de Grafos con Matriz de Incidencia

23

Matrices de Adyacencia en Grafos Dirigidos

24

Análisis de Caminos y Ciclos Eulerianos en Grafos

Árboles

25

Árboles y Tipos de Árboles en Matemáticas Discretas

26

Estructuras de Árboles en Programación y Jerarquías de Datos

27

Conceptos Básicos de Estructuras de Árboles en Informática

28

Árbol de Expansión Mínima: Conexión Óptima de Nodos

29

Tipos de Árboles Binarios y sus Características

30

Recorridos de Árboles: Preorden, Inorden y Posorden

31

Árboles Binarios para Expresiones Aritméticas

32

Transformación de Expresiones Aritméticas en Árboles Binarios

33

Árboles: Altura, Niveles y Recorridos Ordenados

Algoritmos

34

Algoritmo de Prim: Árbol de Expansión Mínimo en Grafos

35

Algoritmo de Dijkstra: Ruta Óptima y Coste Mínimo

36

Algoritmo de Kruskal

37

Algoritmo de Flury: Encontrar Ciclos Eulerianos en Grafos

38

Algoritmo de Flujo Máximo en Redes Dirigidas

39

Algoritmos de Grafos: Prim, Dijkstra, Kruskal y Fleury

Conclusiones

40

Repaso Final de Matemáticas Discretas: Lógica, Conjuntos y Algoritmos

No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

Algoritmo de Dijkstra: Ruta Óptima y Coste Mínimo

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 35

Preguntas 4

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

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.

¿Porqué el profesor les dice arboles y no grafos? A mi se me figura mas a un grafo a que un árbol.

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

Excelente explicación, ahora entiendo un poco más sobre el curso de algoritmos aunque no se trató este tema en específico 😃

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.

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?

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?

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

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

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.

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 !! 😄

Para implementar el algoritmo de Dijkstra en JavaScript, puedes seguir este ejemplo básico: ```javascript function dijkstra(graph, start) { let distances = {}; let visited = new Set(); let unvisited = new Set(Object.keys(graph)); // Inicializa distancias for (let node of unvisited) { distances[node] = Infinity; } distances[start] = 0; while (unvisited.size) { let currentNode = Array.from(unvisited).reduce((a, b) => distances[a] < distances[b] ? a : b); unvisited.delete(currentNode); visited.add(currentNode); for (let neighbor in graph[currentNode]) { let newDist = distances[currentNode] + graph[currentNode][neighbor]; if (newDist < distances[neighbor]) { distances[neighbor] = newDist; } } } return distances; } // Ejemplo de uso const graph = { A: { B: 4, C: 3, E: 7 }, B: { A: 4, D: 6 }, C: { A: 3, D: 11, E: 8 }, D: { B: 6, C: 11, F: 2 }, E: { A: 7, C: 8, F: 9 }, F: { D: 2, E: 9 } }; console.log(dijkstra(graph, 'A')); // { A: 0, B: 4, C: 3, D: 10, E: 7, F: 12 } ``` Este código define una función `dijkstra` que toma un grafo y un nodo de inicio, y devuelve las distancias mínimas desde el nodo inicial a todos los demás nodos.
El algoritmo de Dijkstra se puede implementar en Python de la siguiente manera: ```python import heapq def dijkstra(graph, start): min_heap = [(0, start)] distances = {node: float('infinity') for node in graph} distances[start] = 0 while min_heap: current_distance, current_node = heapq.heappop(min_heap) if current_distance > distances[current_node]: continue for neighbor, weight in graph[current_node].items(): distance = current_distance + weight if distance < distances[neighbor]: distances[neighbor] = distance heapq.heappush(min_heap, (distance, neighbor)) return distances graph = { 'A': {'B': 4, 'C': 3}, 'B': {'A': 4, 'D': 2}, 'C': {'A': 3, 'D': 1, 'E': 5}, 'D': {'B': 2, 'C': 1, 'E': 8}, 'E': {'C': 5, 'D': 8} } print(dijkstra(graph, 'A')) ``` Este código establece un grafo como un diccionario de adyacencia y utiliza una cola de prioridad para calcular las distancias mínimas desde el nodo inicial a todos los demás nodos.
El algoritmo de Dijkstra selecciona la ruta con el menor costo acumulado desde el nodo inicial hasta el nodo final. Si hay dos caminos hacia el nodo f con el mismo peso (11), se selecciona el que se haya encontrado primero en el proceso de exploración, en este caso, el camino a través de abdf, porque se evalúa antes que el otro camino. Esto se debe a que el algoritmo siempre elige el nodo con la distancia más corta disponible para seguir explorando.

Ejercicio demostrativo del Algoritmo de dijkstra

Resumen del Algoritmo de dijkstra

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

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

buen maestro

muy buen contenido… el ejemplo se entendió perfecto

Saludos a todos y a seguir estudiando! 😄

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.

profesor: también podría ser (a -----e-------d------f)

Me encantó.

conocimiento nuevo.
excelente

Excelente