A Python package to find the shortest path in a graph using Ant Colony Optimization (ACO)
Project description
Ant Colony Optimization
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.
🏁 Getting Started
To install the package directly from PyPi:
$ pip install aco_routing
🎈 Usage
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
📦 Contents
Ant
aco_routing.Ant
- An
Ant
that traverses the graph.
ACO
aco_routing.ACO
- The traditional Ant Colony Optimization algorithm that spawns ants at various nodes in the graph and finds the shortest path between the specified source and destination (pseudo code).
Contributing
- Post any issues and suggestions on the GitHub issues page.
- To contribute, fork the project and then create a pull request back to master.
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for aco_routing-1.1.1-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c79e5b21829830c49cbb064b47c42d86124a057a0e66ed81fdcbf91114236a0b |
|
MD5 | c74825f54e89acadaaccad940c6e0a9d |
|
BLAKE2b-256 | ba456163a00ce560bbfefd7bdea051987c999ad24f2a8c5292029ad0c4907f77 |