El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Algoritmo de Dijkstra

Siguiente ►
►

El Algoritmo de Dijkstra es un algoritmo clásico utilizado para encontrar el camino más corto desde un nodo origen a todos los demás nodos en un grafo ponderado. Este algoritmo es fundamental en el campo de la teoría de grafos y tiene aplicaciones prácticas en redes de comunicación, sistemas de navegación y más.

Conceptos Clave

Antes de profundizar en el algoritmo, es importante entender algunos conceptos básicos:

  1. Grafo Ponderado: Un grafo donde cada arista tiene un peso asociado, que representa el costo, la distancia o cualquier otra métrica relevante.
  2. Nodo (o vértice): Un punto en el grafo.
  3. Arista (o borde): Una conexión entre dos nodos en el grafo.
  4. Camino: Una secuencia de aristas que conecta un conjunto de nodos.
  5. Distancia: La suma de los pesos de las aristas en un camino.

Descripción del Algoritmo

El Algoritmo de Dijkstra sigue estos pasos:

  1. Inicialización:

    • Establecer la distancia del nodo origen a sí mismo como 0.
    • Establecer la distancia de todos los demás nodos como infinita.
    • Marcar todos los nodos como no visitados.
    • Establecer el nodo origen como el nodo actual.

  2. Iteración:

    • Para el nodo actual, considerar todos sus vecinos no visitados.
    • Calcular la distancia total desde el nodo origen a cada vecino a través del nodo actual.
    • Si esta distancia es menor que la distancia registrada previamente para el vecino, actualizar la distancia.
    • Marcar el nodo actual como visitado.
    • Seleccionar el nodo no visitado con la distancia más pequeña como el nuevo nodo actual y repetir el proceso hasta que todos los nodos hayan sido visitados.

Ejemplo Práctico

Consideremos el siguiente grafo ponderado:

    A
   / \
  1   4
 /     \
B---2---C
 \     /
  3   1
   \ /
    D

Queremos encontrar el camino más corto desde el nodo A a todos los demás nodos.

Paso a Paso

  1. Inicialización:

    • Distancias: A=0, B=∞, C=∞, D=∞
    • Nodo actual: A

  2. Iteración 1:

    • Vecinos de A: B y C
    • Distancia a B a través de A: 0 + 1 = 1 (actualizar B=1)
    • Distancia a C a través de A: 0 + 4 = 4 (actualizar C=4)
    • Marcar A como visitado.
    • Nodo actual: B (distancia más pequeña)

  3. Iteración 2:

    • Vecinos de B: A, C, D
    • Distancia a C a través de B: 1 + 2 = 3 (actualizar C=3)
    • Distancia a D a través de B: 1 + 3 = 4 (actualizar D=4)
    • Marcar B como visitado.
    • Nodo actual: C (distancia más pequeña)

  4. Iteración 3:

    • Vecinos de C: A, B, D
    • Distancia a D a través de C: 3 + 1 = 4 (no actualizar, ya que D=4)
    • Marcar C como visitado.
    • Nodo actual: D

  5. Iteración 4:

    • Vecinos de D: B, C
    • Todos los vecinos ya han sido visitados.
    • Marcar D como visitado.

Resultado Final

  • Distancias desde A: A=0, B=1, C=3, D=4

Implementación en Python

A continuación se presenta una implementación del Algoritmo de Dijkstra en Python:

import heapq

def dijkstra(graph, start):
    # Inicialización
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        
        # Si la distancia actual es mayor que la registrada, continuar
        if current_distance > distances[current_node]:
            continue
        
        # Considerar todos los vecinos no visitados
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            
            # Si se encuentra una distancia más corta, actualizar
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

# Grafo de ejemplo
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 3},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 3, 'C': 1}
}

# Ejecución del algoritmo
start_node = 'A'
distances = dijkstra(graph, start_node)
print(f"Distancias desde {start_node}: {distances}")

Explicación del Código

  1. Inicialización:

    • distances: Un diccionario que almacena la distancia mínima desde el nodo de inicio a cada nodo.
    • priority_queue: Una cola de prioridad que ayuda a seleccionar el nodo con la distancia más pequeña.

  2. Bucle Principal:

    • Se extrae el nodo con la distancia más pequeña de la cola de prioridad.
    • Si la distancia actual es mayor que la registrada, se continúa con el siguiente nodo.
    • Para cada vecino del nodo actual, se calcula la distancia y se actualiza si es menor que la registrada.

  3. Resultado:

    • El diccionario distances contiene las distancias mínimas desde el nodo de inicio a todos los demás nodos.

Ejercicio Práctico

Ejercicio

Dado el siguiente grafo, implementa el Algoritmo de Dijkstra para encontrar el camino más corto desde el nodo S a todos los demás nodos.

    S
   /|\
  7 | 9
 /  |  \
A---|---B
 \  |  /
  2 | 10
   \|/
    C

Solución

# Grafo de ejemplo
graph = {
    'S': {'A': 7, 'B': 9, 'C': 10},
    'A': {'S': 7, 'C': 2},
    'B': {'S': 9, 'C': 10},
    'C': {'A': 2, 'B': 10, 'S': 10}
}

# Ejecución del algoritmo
start_node = 'S'
distances = dijkstra(graph, start_node)
print(f"Distancias desde {start_node}: {distances}")

Resultado Esperado

Distancias desde S: {'S': 0, 'A': 7, 'B': 9, 'C': 9}

Conclusión

El Algoritmo de Dijkstra es una herramienta poderosa para encontrar caminos más cortos en grafos ponderados. Su comprensión y aplicación son esenciales para resolver problemas complejos en diversas áreas. Asegúrate de practicar con diferentes grafos y escenarios para dominar este algoritmo.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2024. Todos los derechos reservados