Skip to main content

A Python package to find the shortest path in a graph using Ant Colony Optimization (ACO)

Project description

Ant Colony Optimization

Develop Deploy PyPi version Downloads

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

aco_routing-1.1.1.tar.gz (7.6 kB view hashes)

Uploaded Source

Built Distribution

aco_routing-1.1.1-py3-none-any.whl (8.5 kB view hashes)

Uploaded Python 3

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page