Algoritmo de Dijkstra en Python

El algoritmo de Dijkstra es un algoritmo clásico en teoría de grafos utilizado para encontrar el camino más corto desde un nodo de origen a todos los demás nodos en un grafo ponderado (con pesos en las aristas). La lógica del algoritmo de Dijkstra se presenta a continuación:

Definiciones Previas:

• Grafo Ponderado: Es aquel grafo en el que cada arista tiene un peso (o costo) asociado.
• Distancia: Corresponde a la longitud del camino más corto entre dos nodos.
• Nodo de Origen: El nodo desde el cual se inicia la búsqueda del camino más corto.

Pasos del algoritmo

1. Inicialización:
   - Crea un conjunto de nodos no visitados y asigna una distancia inicial de infinito a todos los nodos excepto al nodo de origen, al que se le asigna una distancia de 0.
   • Crea un conjunto vacío de nodos visitados.
2. Bucle Principal:
   - Mientras haya nodos no visitados:
   - Encuentra el nodo no visitado con la distancia mínima del conjunto de nodos no visitados. Llamémoslo nodo_actual.
   - Marca nodo_actual como visitado y lo elimina del conjunto de nodos no visitados.
   • Para cada vecino vecino del nodo_actual que aún no ha sido visitado:
     • Calcula la nueva distancia desde el nodo de origen hasta vecino pasando por nodo_actual.
     • Si esta nueva distancia es menor que la distancia almacenada para vecino, actualiza la distancia almacenada para vecino.
3. Fin del Algoritmo:

• Una vez que todos los nodos hayan sido visitados o el nodo de destino haya sido visitado, el algoritmo termina. Las distancias calculadas representan los caminos más cortos desde el nodo de origen a cada nodo en el grafo.

Definición del código del algoritmo

Una vez vista la lógica del algoritmo, vamos a proceder a la creación del código del mismo. En esta ocasión vamos a trabajar con clases en Python para definir la clase Graph que nos permitirá definir la lógica del algoritmo. Esta clase Graph va a contener los métodos para agregar nodos, agregar aristas y ejecutar el algoritmo de Dijkstra para determinar los caminos más cortos.

Vamos a ver cómo definimos los métodos de la clase Graph para luego verlo todo junto:

Método __init__

Cuando se trabaja con clases en Python, es común definir el método __init__(self) para inicializar la instancia del objeto con valores que se requieran. En este caso vamos a inicializar la instancia con dos atributos, un conjunto para almacenar los nodos y un diccionario para almacenar las aristas.

Nota Cuando se trabaja con clases, es común utilizar la palabra reservada self en la definición de los métodos para recibirla como argumento, ya que esta declaración hace referencia a la clase misma y a través de self puede acceder a todos los componentes de la clase.

def __init__(self):
    self.nodes = set()
    self.edges = {}

Método para agregar nodos

Este método recibe como parámetro el valor del nodo que se quiere agregar y lo inserta en el atributo nodes que definimos en el método __init__. Adicional a esto agrega una entrada en el diccionario de aristas en donde la clave corresponde al valor del nodo y el valor se asigna como una lista vacía, que se usará luego para agregar los nodos a los que está conectado (es decir las aristas).

Nota: La idea de que los nodos sean un objeto del tipo set() es porque deben ser únicos y no deben existir nodos duplicados.

def addNode(self, value):
    self.nodes.add(value)
    self.edges[value] = []

Método para agregar aristas

El método para agregar aristas a más del parámetro self recibe tres parámetros, origin para referirse al nodo de origen, destiny correspondiente al nodo de destino y weight que hace referencia al peso de la arista desde el origen hasta el destino. Esta relación se ingresa en los dos sentidos

def addEdge(self, origin, destiny, weight):
    self.edges[origin].append((destiny, weight))

Método del algoritmo de Dijkstra

Para definir este método se debe recalcar que se utiliza la biblioteca heapq de Python que consiste en un módulo que proporciona implementaciones de colas de prioridad utilizando estructuras de datos de montículos binarios (heaps). Los montículos binarios son estructuras de datos que mantienen una propiedad especial: el elemento en la posición i es siempre menor o igual que los elementos en las posiciones 2i+1 y 2i+2. Esto permite implementar fácilmente colas de prioridad.

Nota: Si se utiliza una cola de prioridad (por ejemplo, un montículo binario) para la implementación del algoritmo de Dijkstra, el tiempo de ejecución es O((V + E) log V), donde V es el número de nodos y E es el número de aristas en el grafo.

    def dijkstra(self, start):
        # Realizamos la inicialización definiendo una distancia de valor infinito
        # a cada uno de los nodos no visitados
        distances = {node: float('infinity') for node in self.nodes}
        # Adignamos la distancia de 0 la nodo de origen
        distances[start] = 0
        # Creamos un conjunto de nodos visitados
        tempQueue = [(0, start)]
        # Iniciamos el bucle principal
        while tempQueue:
            # Obtenemos el nodo con la distancia más baja de la cola
            actualDistance, actualNode = heapq.heappop(tempQueue)
            # Si encontramos una distancia más larga a un nodo, omitimos este nodo
            if actualDistance > distances[actualNode]:
                continue
            for neighbor, weight in self.edges[actualNode]:
                # Calculamos la distancia tentativa al vecino
                distance = actualDistance + weight
                if distance < distances[neighbor]:
                    # Actualizamos la distancia si encontramos un camino más corto
                    distances[neighbor] = distance
                    # Agregamos el vecino a la cola de prioridad
                    heapq.heappush(tempQueue, (distance, neighbor))
        # Devuelve las distancias más cortas desde el nodo de inicio a todos los demás nodos del grafo
        return distances

Clase Graph

Una vez definidos todos los métodos de la clase Graph, vamos a ver cómo quedaría todo junto:

import heapq

class Graph:
    def __init__(self):
        self.nodes = set()
        self.edges = {}

    def addNode(self, value):
        self.nodes.add(value)
        self.edges[value] = []

    def addEdge(self, origin, destiny, weight):
        self.edges[origin].append((destiny, weight))

    def dijkstra(self, start):
        # Realizamos la inicialización definiendo una distancia de valor infinito
        # a cada uno de los nodos no visitados
        distances = {node: float('infinity') for node in self.nodes}
        # Adignamos la distancia de 0 la nodo de origen
        distances[start] = 0
        # Creamos un conjunto de nodos visitados
        tempQueue = [(0, start)]
        # Iniciamos el bucle principal
        while tempQueue:
            # Obtenemos el nodo con la distancia más baja de la cola
            actualDistance, actualNode = heapq.heappop(tempQueue)
            # Si encontramos una distancia más larga a un nodo, omitimos este nodo
            if actualDistance > distances[actualNode]:
                continue
            for neighbor, weight in self.edges[actualNode]:
                # Calculamos la distancia tentativa al vecino
                distance = actualDistance + weight
                if distance < distances[neighbor]:
                    # Actualizamos la distancia si encontramos un camino más corto
                    distances[neighbor] = distance
                    # Agregamos el vecino a la cola de prioridad
                    heapq.heappush(tempQueue, (distance, neighbor))
        # Devuelve las distancias más cortas desde el nodo de inicio a todos los demás nodos del grafo
        return distances

Probando el funcionamiento

Una vez definida la lógica de la clase Graph, podemos realizar pruebas para validar que la implementación funciona de manera correcta. Para esto lo primero que debemos hacer es crear una instancia de la clase:

graph = Graph()

Ahora vamos a crear los nodos de nuestro grafo, para este caso vamos a crear 8 nodos correspondientes a las letras de la A hasta la H.

graph.addNode('A')
graph.addNode('B')
graph.addNode('C')
graph.addNode('D')
graph.addNode('E')
graph.addNode('F')
graph.addNode('G')
graph.addNode('H')

Con los nodos creados podemos definir las aristas con sus respectivos pesos:

graph.addEdge('A', 'B', 4)
graph.addEdge('A', 'C', 9)
graph.addEdge('A', 'E', 7)
graph.addEdge('A', 'F', 3)
graph.addEdge('A', 'G', 11)
graph.addEdge('A', 'H', 15)
graph.addEdge('B', 'C', 4)
graph.addEdge('B', 'D', 4)
graph.addEdge('B', 'E', 2)
graph.addEdge('B', 'G', 9)
graph.addEdge('C', 'D', 8)
graph.addEdge('C', 'F', 2)
graph.addEdge('D', 'G', 11)
graph.addEdge('D', 'F', 8)
graph.addEdge('D', 'E', 5)
graph.addEdge('D', 'H', 4)
graph.addEdge('E', 'G', 3)
graph.addEdge('E', 'H', 14)

Con esto tenemos nuestro grafo listo, y se encuentra configurado de la siguiente manera:

Ahora debemos definir cuál va a ser nuestro punto de partida y con eso calcular las distancias:

inicio = 'A'
distancias = graph.dijkstra(inicio)

Por último vamos a mostrar cuáles son los caminos más cortos desde el nodo de partida A hacia el resto de los nodos, para eso recorremos todos los elementos de las distancias e imprimimos el resultado:

print("Distancias más cortas desde el nodo", inicio)
for nodo, distancia in distancias.items():
    print(f"A -> {nodo}: {distancia}")

Y obtenemos el siguiente resultado:

Distancias más cortas desde el nodo A
A -> C: 8
A -> G: 9
A -> B: 4
A -> E: 6
A -> D: 8
A -> F: 3
A -> H: 12
A -> A: 0