El Algoritmo de Dijkstra: Qué es, Cómo Funciona y Dónde se utiliza

Con él, los navegadores, los robots y los personajes de los videojuegos construyen rutas.

Todos usamos aplicaciones de navegación: ingresamos el punto de inicio y el punto final, y el programa construye la ruta más óptima a su juicio. Para ello, utiliza los llamados algoritmos de búsqueda de la ruta más corta. Hoy hablaremos de los más populares de ellos: los algoritmos de Dijkstra y A*. Descubriremos cómo funcionan, dónde se aplican y en qué se diferencian entre sí.

El principio: la teoría de los grafos

El algoritmo de Dijkstra es un método para encontrar las rutas más cortas desde un vértice de un grafo hasta todos los demás.

Un grafo es una estructura matemática que consta de vértices (nodos) y aristas (conexiones) entre ellos. Las aristas pueden tener dirección y también pesos: números que indican la fuerza de las conexiones con los vértices.

Los grafos se utilizan para representar objetos, sus interconexiones y las relaciones entre ellos. Por ejemplo, en forma de grafo, se puede representar una red social, donde los vértices son los usuarios, las conexiones de amistad entre ellos son las aristas, y los pesos son, por ejemplo, la frecuencia de intercambio de mensajes.

Pero, por supuesto, el significado práctico de los grafos no se limita a las redes sociales. Por ejemplo, con su ayuda, puedes modelar las conexiones entre:

• Páginas web
• Calles y cruces al diseñar una red vial
• Genes, proteínas y moléculas en bioinformática
• Puntos de entrega de mercancías en logística
• Puntos de movimiento de robots en robótica

Cómo funciona el algoritmo de Dijkstra

La idea del algoritmo de Dijkstra es que podemos encontrar las distancias más pequeñas desde el vértice inicial del grafo hasta todos los demás.

Conociendo estas distancias, se puede construir la ruta más corta entre el punto de inicio y otros puntos.

Supongamos que tenemos varias ciudades conectadas por carreteras. Llamémoslas A, B, C, D, E, F. Los números cerca de las aristas son las distancias entre las ciudades en millas.

Ahora intentemos encontrar la ruta más corta, digamos, de A a C. Parece bastante simple: comparamos todos los caminos posibles y elegimos el más corto: A → B → C. Una simple enumeración, nada de rocket science.

Las dificultades comienzan cuando hay demasiados datos. Si hubiera más de 26 ciudades en nuestro mapa, incluso la computadora más potente necesitaría miles de millones de años para calcular todas las opciones.

El algoritmo de Dijkstra funciona de manera diferente: no enumera «mentalmente» todas las opciones posibles, sino que construye la ruta paso a paso. En cada paso, el algoritmo elige el vértice menos distante y se mueve hacia él, luego hacia el siguiente, y así sucesivamente hasta llegar al destino.

El significado clave es este: si en cada etapa se toman decisiones óptimas, la decisión final, lo más probable, también será óptima. Los algoritmos que funcionan de acuerdo con este principio se llaman algoritmos voraces.

Volvamos a nuestro grafo con ciudades. Encontremos con la ayuda del algoritmo de Dijkstra las distancias más cortas de A a B, C, D, E y F.

Paso 1. Establezcamos una estimación inicial del camino hasta A para cada vértice. Para la propia A, la estimación es 0, al resto se les asigna infinito, ya que aún no conocemos sus valores.

Consideremos los vértices adyacentes a A, es decir, aquellos que están conectados a A mediante aristas directamente. Estos son B y E: sus distancias a A son 7 y 4 respectivamente. Dado que estos valores, obviamente, son menores que el infinito, los actualizaremos en el diagrama. Consideraremos el vértice A como visitado, lo coloreamos y ya no lo consideramos.

Ahora pasemos al vértice no visitado con la distancia más pequeña a A. Este es el vértice E. Los vértices adyacentes a él no visitados son F y D. Sus distancias a A serán iguales a la estimación de E (es decir, la distancia de E a A) más los pesos de las aristas de E a estos vértices. Resulta así:

• Para F: 4 + 3 = 7
• Para D: 4 + 8 = 12

Las distancias obtenidas son menores que las estimaciones anteriores, por lo que las registraremos cerca de los vértices F y D. Consideraremos el vértice E como visitado. Lo coloreamos.

Lo siguiente, por analogía: el algoritmo elige los vértices no visitados con la estimación más pequeña y calcula las distancias desde los vértices adyacentes a él hasta A. Y esto continúa hasta que el algoritmo calcula las distancias más cortas hasta A para todos los vértices.

¡Listo! Ahora podemos construir la ruta más corta de A a cualquier otro vértice. Por ejemplo:

• De A a F: A — E — F
• De A a D: A — E — D
• De A a C: A — B — C

Cómo surgió el algoritmo de Dijkstra

El algoritmo de búsqueda de la ruta más corta fue desarrollado por el científico holandés Edsger Dijkstra en 1956. En ese momento, estaba buscando una forma de demostrar las capacidades de la nueva computadora ARMAC y estaba buscando un problema que ARMAC pudiera resolver y que fuera comprensible para las personas que no estaban familiarizadas con las computadoras.

Dijkstra tomó el problema de encontrar la ruta más corta y desarrolló un algoritmo para resolverlo. Basándose en el algoritmo, desarrolló un programa para construir rutas entre ciudades en un mapa de transporte de los Países Bajos.

Más tarde, Dijkstra contó:

“Una vez, mi novia y yo bebíamos café en la terraza de un café en Ámsterdam. Allí, en unos veinte minutos, desarrollé el algoritmo para encontrar la ruta más corta. Fue publicado tres años después, en 1959.

Una de las razones por las que el algoritmo resultó tan hermoso fue que lo creé en mi mente, sin lápiz ni papel. Luego me enteré de que una de las ventajas de este tipo de diseño es que, al hacerlo, intentas evitar al máximo las dificultades.

Este algoritmo se convirtió, para mi sorpresa, en una de las piedras angulares de mi fama».

Edsger Dijkstra
en una entrevista con Philip L. Fran

Ejemplo de implementación del algoritmo de Dijkstra en Python

Hemos estudiado la teoría, ahora escribamos el código que implementa el algoritmo de Dijkstra en el lenguaje Python. Como ejemplo, calcularemos la distancia desde el vértice A hasta otros vértices en nuestro grafo.

Para trabajar, necesitamos heapq, uno de los módulos de la biblioteca estándar de Python, diseñado para trabajar con montículos. Un montículo es una estructura de datos donde cada nodo padre tiene un valor menor o igual a cualquiera de sus nodos hijos.

Creemos la función dijkstra con los argumentos:

• graph: el grafo dado
• start: el vértice inicial

Dentro de la función, creamos un diccionario distances para almacenar las distancias desde el vértice inicial hasta todos los demás. También creamos una cola de prioridad priority_queue para elegir vértices con la distancia actual más pequeña.

import heapq


def dijkstra(graph, start):
    # Inicialización del diccionario para almacenar distancias
    # hasta cada vértice. Al principio, todas las distancias son infinitas.
    distances = {vertex: float('infinity') for vertex in graph}

    # La distancia hasta el vértice inicial es 0.
    distances[start] = 0

    # Creemos una cola de prioridad para almacenar vértices y sus distancias.
    priority_queue = [(0, start)]

Luego, el algoritmo en el ciclo actualiza las distancias hasta los vértices adyacentes hasta que encuentra las distancias más cortas para todos los vértices. El resultado se muestra como un diccionario, donde las claves son vértices y los valores son distancias hasta ellos desde el punto A.

    while priority_queue:
        # Extraemos el vértice con la distancia más pequeña de la cola.
        current_distance, current_vertex = heapq.heappop(priority_queue)

        # Si la distancia actual hasta el vértice ya es mayor que la distancia almacenada, lo ignoramos.
        if current_distance > distances[current_vertex]:
            continue

        # Consideremos todos los vértices adyacentes al vértice actual.
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            # Si encontramos un camino más corto hasta el vecino, actualicemos la distancia.
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

Ahora calculemos para nuestro grafo las distancias más cortas de A a los demás vértices. Representemos el grafo como un diccionario, donde las claves son vértices y los valores son diccionarios con los vértices adyacentes y los pesos de las aristas.

# Ejemplo de uso:
graph = {
    'A': {'B': 4, 'C': 7},
    'B': {'A': 4, 'D': 2, 'E': 8},
    'C': {'A': 7, 'D': 2, 'E': 5},
    'D': {'B': 2, 'C': 2, 'E': 1,'F': 4},
    'E': {'C': 5, 'D': 1, 'F': 11},
    'F': {'B': 8, 'D': 4, 'E': 11}
}

Llamemos a la función dijkstra con el vértice inicial A y mostremos el resultado en la consola.

result = dijkstra(graph, 'A')
# Mostremos el resultado.
print("Las distancias más cortas hasta cada vértice:")
for vertex, distance in result.items():
    print(f"Hasta el vértice {vertex}: {distance}")

¡Bingo!

Las distancias más cortas hasta cada vértice:
Hasta el vértice A: 0
Hasta el vértice B: 4
Hasta el vértice C: 7
Hasta el vértice D: 6
Hasta el vértice E: 7
Hasta el vértice F: 10

Qué es el algoritmo A*

Otro algoritmo conocido para encontrar la ruta más corta es A* (o La heurística de búsqueda A*, se lee como «A estrella» o «A star»). En esencia, es una extensión del algoritmo de Dijkstra con funciones adicionales para mejorar la velocidad. Se desarrolló A* en 1968, se utiliza hasta ahora en diversas áreas: desde la robótica hasta la navegación y el desarrollo de juegos.

Al igual que el algoritmo de Dijkstra, A* busca la distancia desde el punto de inicio hasta el punto final. Pero, a diferencia de este último, no solo tiene en cuenta la distancia desde el punto actual hasta el inicial, sino también la estimación heurística de esta distancia. En este contexto, «heurística» significa «aproximada»: la función no determina la distancia exacta desde el punto hasta el objetivo, sino que le indica al algoritmo la magnitud aproximada.

Por ejemplo, necesitamos encontrar la ruta más corta desde la ciudad A hasta la ciudad B en el mapa. Como heurística, podemos utilizar la distancia «en línea recta» (es decir, la «distancia euclidiana») desde el punto actual hasta el punto B. Esto permitirá estimar la longitud del camino entre el punto actual y el objetivo.

En el gráfico anterior se muestran las distancias heurísticas desde los puntos intermedios hasta el punto final en el mapa, sin tener en cuenta las carreteras existentes.

Otra heurística popular es la distancia de Manhattan. Su nombre proviene del sistema de calles en la isla de Manhattan en Nueva York. Esta es una red de calles que se cruzan en ángulo recto, lo que la hace similar a una tabla. Para llegar de un punto a otro, hay que moverse a lo largo de las calles. Si representamos estas calles como una cuadrícula de coordenadas, podemos movernos solo a lo largo de los ejes X e Y, pero no en diagonal.

Si tenemos dos puntos con coordenadas (x1, y1) y (x2, y2), la distancia de Manhattan entre ellos (M) se calcula mediante la siguiente fórmula:

Intentemos comprenderlo con un ejemplo. Supongamos que tenemos un punto A con coordenadas (2, 8) y un punto B con coordenadas (4, 3).

Sustituyendo las coordenadas en la fórmula, resulta que la distancia de Manhattan es M = ∣4−2∣ + ∣3−8∣ = 2 + 5 = 7.

La idea principal del algoritmo A* es determinar dos valores para cada vértice en el grafo:

• g(n): la longitud del camino desde el vértice inicial hasta el vértice actual n.
• h(n): la estimación heurística de la longitud desde el vértice actual n hasta el objetivo.

En cada paso, el algoritmo A* elige el vértice con la suma más pequeña g(n) + h(n) y examina sus vecinos. Esto continúa hasta que el algoritmo alcanza el objetivo final.

Implementación del algoritmo A* en Python

Intentemos escribir A* en Python para un grafo con heurística en forma de distancia de Manhattan. Aquí, la función manhattan_distance calcula la distancia de Manhattan entre dos puntos, y astar implementa el algoritmo A* utilizando esta distancia.

import heapq


# Función para calcular la distancia de Manhattan entre dos puntos
def manhattan_distance(point1, point2):
    return abs(point1[0] - point2[0]) + abs(point1[1] - point2[1])

Implementación del algoritmo A*:

def astar(grid, start, goal):
    # Inicialización de los diccionarios para almacenar los costes y los puntos anteriores
    cost = {start: 0}
    came_from = {start: None}


    # Cola de prioridad para almacenar puntos y sus evaluaciones (prioridades)
    priority_queue = [(0, start)]


    while priority_queue:
        # Extracción del punto con la evaluación mínima
        current_cost, current_point = heapq.heappop(priority_queue)

        # Si se alcanza el punto objetivo, finalizamos el algoritmo
        if current_point == goal:
            break


        # Consideración de los puntos adyacentes
        for neighbor in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            x, y = current_point[0] + neighbor[0], current_point[1] + neighbor[1]

            new_cost = cost[current_point] + 1 # Coste de desplazamiento a una celda



            # Comprobación de la presencia de un obstáculo y actualización del coste si el nuevo camino es más corto
            if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == 0:
                if (x, y) not in cost or new_cost < cost[(x, y)]:
                    cost[(x, y)] = new_cost
                    priority = new_cost + manhattan_distance((x, y), goal)  
# Evaluación para la prioridad
                    heapq.heappush(priority_queue, (priority, (x, y)))
                    came_from[(x, y)] = current_point

Recuperación del camino:

path = []
    current = goal
    while current:
        path.append(current)
        current = came_from[current]
    path.reverse()


    return path

Ejecución del algoritmo A*. Definición de una cuadrícula de 5 × 5. Los obstáculos se indican con unos en la cuadrícula.

grid = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 0, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0]
]


# Punto inicial y punto final
start = (0, 0)
goal = (4, 4)


result_path = astar(grid, start, goal)


# Salida del resultado
print("Camino de A a B:")
for point in result_path:
    print(point)

Como resultado de la ejecución, obtenemos:

Camino de A a B:
(0, 0)
(0, 1)
(0, 2)
(0, 3)
(0, 4)
(1, 4)
(2, 4)
(3, 4)
(4, 4)

Este código implementa A* para buscar la ruta más corta en una cuadrícula dada utilizando la distancia de Manhattan como función heurística. Como resultado, muestra la ruta más corta desde el punto A hasta el B.

Comparación de los algoritmos de Dijkstra y A*

La elección entre estos algoritmos depende de la tarea específica y la información disponible.

Comparamos:

• El algoritmo de Dijkstra se utiliza para encontrar la ruta más corta desde el vértice inicial del grafo hasta todos los demás. El algoritmo A* se utiliza para encontrar la ruta más corta desde el vértice inicial hasta uno dado, teniendo en cuenta la estimación heurística de la distancia.
• El algoritmo de Dijkstra considera todos los vértices de manera equivalente y siempre elige el vértice con la distancia más pequeña hasta él. El algoritmo A*, además de esto, utiliza adicionalmente la heurística. Esto lo hace más eficiente para grafos grandes o cuando hay información sobre la magnitud aproximada de la distancia hasta el objetivo.
• El algoritmo de Dijkstra puede ser lento para grafos grandes, ya que explora todos los vértices. El algoritmo A* funciona más rápido en grafos grandes gracias a la heurística, lo que le permite reducir la cantidad de vértices examinados.

Por lo tanto, el algoritmo de Dijkstra será más eficiente donde sea necesario encontrar las rutas más cortas desde un vértice hasta todos los demás y no haya información sobre la distancia aproximada hasta el objetivo. Si existe información heurística que pueda ayudar a acelerar la búsqueda, entonces la mejor opción sería A*.