Unable to find optimal solution for Undirected Graph

[Jaykingamez]

Thanks for solving the previous issue.

I'm trying to replicate the paper "Application of Ant Colony Algorithm in Finding Shortest Paths in Mobile Games".

I notice that this library is specifically meant to deal with directed graphs, so perhaps I am trying to use the wrong tool.

from aco_routing import ACO
import networkx as nx
import matplotlib.pyplot as plt

G = nx.Graph()
# North of map
G.add_edge("HQ", "A", cost=1)
G.add_edge("A", "B", cost=1)
G.add_edge("B", "?North", cost=1)
G.add_edge("?North", "G", cost=1)
G.add_edge("G", "OGAS", cost=1)
# South of map
G.add_edge("HQ", "C", cost=1)
G.add_edge("C", "D", cost=1)
G.add_edge("D", "Helipad", cost=1)
G.add_edge("Helipad", "OGAS", cost=1)
G.add_edge("C", "E", cost=1)
G.add_edge("E", "?South", cost=1)
G.add_edge("?South", "Helipad", cost=1)

source = "OGAS"
destination = "HQ"

aco = ACO(G, ant_max_steps=100, num_iterations=100, ant_random_spawn=True)
# aco.evaporation_rate = 0
# aco.beta = 0

dijkstra_path = nx.dijkstra_path(G, source, destination)
dijkstra_cost = nx.path_weight(G, dijkstra_path, "cost")

aco_path, aco_cost = aco.find_shortest_path(
    source=source,
    destination=destination,
    num_ants=100,
)

print(f"ACO - path: {aco_path}, cost: {aco_cost}")
print(f"Dijkstra - path: {dijkstra_path}, cost: {dijkstra_cost}")
# nx.draw(G, with_labels=True, font_weight='bold')
# plt.show()

In this code, aco always returns the unoptimal solution. Is it due to the fact that the code is meant for directed graphs?

[hasnainroopawalla]

Hi, @Jaykingamez, in response to your question about whether the code is specifically designed for directed graphs, the answer is no.

Ant Colony Optimization is a probabilistic algorithm, which means it may not always lead to the most optimal solution. I would use Dijkstra's algorithm as a baseline to compute the optimal path.