A Python package to find the shortest path in a graph using Ant Colony Optimization (ACO).
➡️ Check out my Medium article for a detailed walkthrough 🚀
The Ant colony Optimization algorithm is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs (source).
This implementation of the ACO algorithm uses the NetworkX graph environment.
$ pip install aco_routing
Check out: example.py
Import all the dependencies:
from aco_routing import ACO
import networkx as nx
Create a NetworkX.Graph
object with nodes and edges:
G = nx.DiGraph()
G.add_edge("A", "B", cost=2)
G.add_edge("B", "C", cost=2)
G.add_edge("A", "H", cost=2)
G.add_edge("H", "G", cost=2)
G.add_edge("C", "F", cost=1)
G.add_edge("F", "G", cost=1)
G.add_edge("G", "F", cost=1)
G.add_edge("F", "C", cost=1)
G.add_edge("C", "D", cost=10)
G.add_edge("E", "D", cost=2)
G.add_edge("G", "E", cost=2)
Use ACO to find the shortest path and cost between the source
and destination
:
aco = ACO(G, ant_max_steps=100, num_iterations=100, ant_random_spawn=True)
aco_path, aco_cost = aco.find_shortest_path(
source="A",
destination="D",
num_ants=100,
)
Output:
ACO path: A -> H -> G -> E -> D
ACO path cost: 8.0
aco_routing.Ant
Ant
that traverses the graph.aco_routing.ACO