En otro artículo, «Algoritmo para saber si existe un camino posible», vimos como encontrar el camino más corto entre 2 nodos de un grafo. Funciona muy bien hasta que el esfuerzo entre los nodos no son iguales. En el mundo real, no tardo el mismo tiempo de ir desde mi casa al trabajo que de mi casa a la panadería (a no ser que trabajes en una panadería, claro). El costo es el tiempo que empleo, el tiempo en este caso. El camino más corto ya no es la ruta con menos nodos, sino la ruta con menos esfuerzo.
Problema
Mi gato acaba de entrar en casa con un apretón. ¡Seguro que ha comido en la calle algo que no debía! Bigotes necesita encontrar el camino más rápido para llegar al arenero. En su peludita cabeza hay una imagen mental de la casa con todo lujo de detalles, incluyendo cuantos segundos tarda en llegar de un sitio a otro.
¿Cómo encuentra el camino más corto? ¡Las combinaciones son enormes! No puede calcularlas todas a la vez. Necesita ayuda. ¡Y rápido!
El algoritmo de Dijkstra es uno de los más populares y utilizados para encontrar el camino más corto entre dos nodos de un grafo. Su única limitación es que no puede ser utilizado en grafos con pesos negativos. Si necesitas un algoritmo que pueda manejar pesos negativos, puedes utilizar el algoritmo de Bellman-Ford.
No vamos a entrar en detalles como funciona, hay muchos recursos en internet que te pueden ayudar, pero si trabajaremos en su implementación en Python. Si entiendes el proceso, será fácil en portarlo a otros lenguajes.
Implementación
Necesitamos 3 mapas para almacenar la información:
graph: Un mapa con los nodos y sus vecinos con el coste de ir de un nodo a otro. Si un nodo no tiene vecinos, se le asignaNone.costs: Un mapa con los costes de ir del nodo inicial al nodo actual. Inicialmente, todos los nodos tienen un coste infinito, excepto el nodo inicial que tiene un coste de 0. A medida que se va calculando el coste de ir de un nodo a otro, se va actualizando sus valores.parents: Un mapa con los padres de cada nodo. Inicialmente, todos los nodos tienen como padre el nodo inicial. Es necesario para ir reconstruyendo el camino más corto a medida que se realizan los cálculos.
Por ejemplo, partimos con el siguiente grafo:
Lo representamos en Python de la siguiente manera:
from typing import Dict
graph: Dict[str, Dict[str, int | float] | None] = {
"start": {"a": 5, "b": 2},
"a": {"c": 4, "d": 2},
"b": {"a": 8, "d": 7},
"c": {"d": 6, "end": 3},
"d": {"end": 1},
"end": None,
}
Cada nodo almacena que vecinos tiene y el coste de ir de un nodo a otro. Por ejemplo, el nodo start tiene dos vecinos, a y b, con un coste de 5 y 2 respectivamente. El nodo end no tiene vecinos, por lo que se le asigna None. La dirección es importante, el nodo a no tiene como vecino al nodo b, pero el nodo b si tiene como vecino al nodo a.
Ahora anotamos, en otro mapa, los costes de ir de un nodo a otro:
from typing import Dict
from math import inf as infinity
costs: Dict[str, int | float] = {
"a": 5,
"b": 2,
"c": infinity,
"d": infinity,
"end": infinity,
}
La única información que disponemos del coste total de un nodo a otro, es desde el inicio al nodo a y b. Llegar al resto de nodos (desde el inicio) es infinito, debido a que no hemos sumado (calculado) ningún coste.
Ahora necesitamos anotar el padre óptimo para llegar a cada nodo. Al igual que antes, la única información que disponemos es desde el inicio al nodo a y b.
from typing import Dict
parents: Dict[str, str] = {
"a": "start",
"b": "start",
}
El resto de padres los iremos calculando, y añadiendo, a medida que vamos calculando los costes.
Con las variables definidas, ya podemos empezar a trabajar.
La implementación del algoritmo de Dijkstra en Python, la dividiremos en 3 funciones:
find_lowest_cost_node: Encuentra el nodo con el menor coste encosts. En caso de ya haber sido procesado, lo ignorará.update_costs: Actualiza los costes y padres de los nodos. Utiliza la funciónfind_lowest_cost_nodepara encontrar el nodo con el menor coste.find_path: Cuando termineupdate_costs, ya estará en nuestro poder los padres más baratos para llegar a cada nodo, pero no aún no conocemos el camino final. Crearemos una función que se encargará de realizar el camino inverso, desde el final al inicio, anotando los nodos con los padres óptimos. Devolviéndonos, ahora sí, el camino más corto.
Para implementar find_lowest_cost_node, podríamos escribirlo de la siguiente forma:
from typing import Dict, List
from math import inf as infinity
def find_lowest_cost_node(
costs: Dict[str, int | float], nodes_to_ignore: List[str] or None = None
) -> str | None:
"""
Find the lowest cost node in the costs dictionary
:param costs: The costs
:param nodes_to_ignore: The nodes to ignore
:return: The lowest cost node
"""
# Default values
# Fix anti-pattern: Using a mutable default value as an argument
# Source: https://docs.quantifiedcode.com/python-anti-patterns/correctness/mutable_default_value_as_argument.html
if nodes_to_ignore is None:
nodes_to_ignore = []
# Ignore infinity or nodes to ignore
costs_filtered = costs.copy()
for key, cost in costs.items():
if cost == infinity or key in nodes_to_ignore:
del costs_filtered[key]
# If there are no costs left
if len(costs_filtered) == 0:
return None
# Find the lowest cost node
def find_min_cost(costs: Dict[str, int | float]) -> Dict[str, int | float]:
if len(costs) == 1:
return costs
cost_keys = list(costs.keys())
if costs[cost_keys[-1]] < costs[cost_keys[0]]:
del costs[cost_keys[0]]
else:
del costs[cost_keys[-1]]
return find_min_cost(costs)
return tuple(find_min_cost(costs_filtered))[0]
He usado un enfoque recursivo. Si no te gusta, puedes cambiarlo por un bucle while o for. Los pasos son los siguientes:
- Ignorar los nodos con coste infinito o los que ya han sido procesados.
- Si no hay nodos con coste, devolver
None. - Encontrar el nodo con el menor coste y devolverlo.
Si lo deseas, puedes realizar algunos tests para comprobar que funciona correctamente:
assert find_lowest_cost_node({"a": 6, "b": 2, "end": infinity}) == "b"
assert find_lowest_cost_node({"a": 6, "b": 2, "end": infinity}, ["b"]) == "a"
assert find_lowest_cost_node({"a": 6, "b": 2, "end": infinity}, ["a", "b"]) is None
assert find_lowest_cost_node({"end": infinity}, ["a"]) is None
assert find_lowest_cost_node({"end": infinity}, []) is None
assert find_lowest_cost_node({}, []) is None
Para implementar update_costs, una posible solución podría ser:
from typing import Dict, List
def update_costs(
graph: Dict[str, Dict[str, int | float] | None],
costs: Dict[str, int | float],
parents: Dict[str, str],
processed: List[str] or None = None,
) -> Dict[str, str] or None:
"""
Update the costs and parents dictionaries using Dijkstra algorithm
:param graph: The graph
:param costs: The costs
:param parents: The parents
:param processed: The processed nodes
:return: List of nodes from the start node to the end node with their parents
"""
# Default values
# Fix anti-pattern: Using a mutable default value as an argument
# Source: https://docs.quantifiedcode.com/python-anti-patterns/correctness/mutable_default_value_as_argument.html
if processed is None:
processed = []
# Find the start node: the node with the lowest cost
node: str | None = find_lowest_cost_node(costs, processed)
# While there are nodes to process
while node and graph[node] is not None:
# Get the cost of the current node
cost = costs[node]
# Get the neighbors of the current node
neighbors = graph[node]
# Go through all the neighbors
if neighbors:
for node_neighbor, cost_neighbor in neighbors.items():
# Calculate the new cost: current node cost + neighbor cost
new_cost = cost + cost_neighbor
# If it's cheaper to get to the neighbor through the current node
if costs[node_neighbor] > new_cost:
# Update the cost of the neighbor
costs[node_neighbor] = new_cost
# This node becomes the new parent for the neighbor:
parents[node_neighbor] = node
# Mark the node as processed
processed.append(node)
# Go to the next node
node = find_lowest_cost_node(costs, processed)
return parents
En este caso, debes seguir más pasos:
- Encontrar el nodo con el menor coste. Si no hay nodos, terminar. Si el nodo no tiene vecinos, terminar. Usamos
find_lowest_cost_nodepara ello. - Calcular el coste de ir de un nodo a otro. Si es más barato, actualizar el coste y lo añadimos a la lista de padres. Este paso es muy importante, ya que es el que nos permitirá encontrar el camino más corto.
- Marcar el nodo como procesado. Para ello lo añadimos a la lista
processed. - Volver al paso 1.
- Cuando no haya más nodos, devolver los padres.
Para crear los tests, esperaremos a tener la función find_path implementada.
Ahora vamos a implementar find_path, la función que nos devolverá el camino más corto recorriendo inversamente los padres de cada nodo:
def find_path(
parents: Dict[str, str], start: str or None = None, end: str or None = None
) -> List[str]:
"""
Find the path from the start node to the end node
:param parents: The parents
:param start: The start node
:param end: The end node
:return: List of nodes from the start node to the end node
"""
if start is None:
start = "start"
if end is None:
end = "end"
if start == end:
return [start]
return find_path(parents, start, parents[end]) + [end]
Repasemos los pasos que se han seguido:
- Si no se ha especificado el nodo de inicio, se asigna
start. - Si no se ha especificado el nodo final, se asigna
end. - Si el nodo de inicio es igual al nodo final, devolver una lista con el nodo de inicio. En otras palabras, hemos llegado al final.
- Llama a
find_path, la función donde estamos, con el nodo de inicio y con el parámetroendel valor del padre. A lo que devuelva, añade el nodo final. Si has trabajado previamente con recursividad, este paso te resultará sencillo de entender. En caso contrario, puedes crear una versión iterativa con un buclewhile.
Los test rápidos podrían ser los siguientes:
assert find_path({"a": "start", "b": "a", "end": "b"}) == ["start", "a", "b", "end"]
assert find_path({"a": "init", "b": "a", "fin": "b"}, "init", "fin") == ["init", "a", "b", "fin"]
assert find_path({"c": "a", "a": "b", "b": "start", "end": "d", "e": "f", "f": "g", "d": "c"}) == ["start", "b", "a", "c", "d", "end"]
Para orquestar las funciones, creamos una última función:
def dijkstra_algorithm(
graph: Dict[str, Dict[str, int | float] | None],
costs: Dict[str, int | float],
parents: Dict[str, str]
) -> Dict[str, str] or None:
"""
Dijkstra algorithm
Find the lowest cost path from the start node to the end node
:param graph: The graph
:param costs: The costs
:param parents: The parents
:return: List of nodes from the start node to the end node with their parents
"""
return find_path(update_costs(graph, costs, parents))
¡Ya podemos probarlo!
dijkstra_algorithm(graph, costs, parents)
# ["start", "a", "d", "end"]
El camino más corto es pasar por los nodos start, a, d y end. ¡Perfecto!
Puedes convertirlo en un pequeño test.
test_a_graph: Dict[str, Dict[str, int | float] | None] = {
"start": {"a": 5, "b": 2},
"a": {"c": 4, "d": 2},
"b": {"a": 8, "d": 7},
"c": {"d": 6, "end": 3},
"d": {"end": 1},
"end": None,
}
test_a_costs: Dict[str, int | float] = {
"a": 5,
"b": 2,
"c": infinity,
"d": infinity,
"end": infinity,
}
test_a_parents: Dict[str, str] = {"a": "start", "b": "start"}
output = dijkstra_algorithm(test_a_graph, test_a_costs, test_a_parents)
assert output == ["start", "a", "d", "end"]
He incluso puedes probar con otros grafos:
test_b_graph: Dict[str, Dict[str, int | float] | None] = {
"start": {"a": 10},
"a": {"b": 20},
"b": {"c": 1, "end": 30},
"c": {"a": 1},
"end": None,
}
test_b_costs: Dict[str, int | float] = {
"a": 10,
"b": infinity,
"c": infinity,
"end": infinity,
}
test_b_parents: Dict[str, str] = {"a": "start"}
test_b_output = dijkstra_algorithm(test_b_graph, test_b_costs, test_b_parents)
assert test_b_output == ["start", "a", "b", "end"]
test_c_graph: Dict[str, Dict[str, int | float] | None] = {
"start": {
"a": 6,
"b": 2,
},
"a": {"end": 1},
"b": {
"a": 3,
"end": 5,
},
"end": None,
}
test_c_costs: Dict[str, int | float] = {
"a": 6,
"b": 2,
"end": infinity,
}
test_c_parents: Dict[str, str] = {
"a": "start",
"b": "start",
}
test_c_output = dijkstra_algorithm(test_c_graph, test_c_costs, test_c_parents)
assert test_c_output == ["start", "b", "a", "end"]
Si todos los test pasan, ¡enhorabuena! Has implementado con éxito el algoritmo de Dijkstra en Python.
Solución
¿Qué pasa con el gato? ¡No te preocupes! Ya le podemos ayudar.
graph_home: Dict[str, Dict[str, int | float] | None] = {
"start": {
"pasillo": 6,
"dormitorio": 10,
"terraza": 4,
},
"pasillo": {
"cocina": 1,
},
"dormitorio": {
"recibidor": 3,
},
"banyo": {
"dormitorio": 2,
"trastero": 1,
},
"terraza": {
"banyo": 3,
"trastero": 8,
},
"cocina": {
"dormitorio": 7,
"recibidor": 9,
},
"trastero": {
"recibidor": 6,
"garaje": 4,
},
"comedor": {
"tejado": 3,
},
"recibidor": {
"comedor": 2,
"tejado": 7,
},
"garaje": {
"recibidor": 3,
"end": 10,
},
"tejado": {
"end": 1,
},
"end": None,
}
costs_home: Dict[str, int | float] = {
"pasillo": 6,
"dormitorio": 10,
"terraza": 4,
"cocina": infinity,
"banyo": infinity,
"comedor": infinity,
"tejado": infinity,
"recibidor": infinity,
"trastero": infinity,
"garaje": infinity,
"end": infinity,
}
parents_home: Dict[str, str] = {
"pasillo": "start",
"dormitorio": "start",
"terraza": "start",
}
dijkstra_algorithm(graph_home, costs_home, parents_home)
# ['start', 'terraza', 'banyo', 'dormitorio', 'recibidor', 'comedor', tejado, 'end']
El gato debe ir a la terraza, luego al baño, al dormitorio, al recibidor, al comedor, al tejado y… finalmente al arenero.
¡Esperemos que llegue sin manchar nada!
Conclusiones
El algoritmo de Dijkstra no solo es útil para ayudar a que los felinos lleguen a sus cuartos de baño. Son altamente utilizados en la industria, como en la planificación de rutas (GPSs), videojuegos (juegos de estrategia), redes de comunicación (routers) y en muchos otros campos. Conocerlo y saber implementarlo te permitirá resolver problemas complejos de una manera sencilla.
Si te ha gustado el artículo, no dudes en compartirlo en tus redes. ¡Hasta la próxima!
{{ comments.length }} comentarios