network/a_star library

🎯 A* Algorithm (Optimal Path Finding with Heuristics)

An informed search algorithm that finds the shortest path between two nodes using a heuristic function to guide the search. A* is optimal when the heuristic is admissible (never overestimates the actual cost).

  • Time Complexity: O(b^d) where b is branching factor, d is depth
  • Space Complexity: O(b^d) for storing the frontier
  • Optimality: Guaranteed when heuristic is admissible
  • Completeness: Always finds a solution if one exists

The algorithm uses a priority queue to explore the most promising paths first, combining the actual cost from start (g-score) with the estimated cost to goal (h-score).

Example:

final graph = <String, Map<String, num>>{
  'A': {'B': 1, 'C': 4},
  'B': {'D': 5, 'E': 2},
  'C': {'D': 3, 'F': 6},
  'D': {'G': 2},
  'E': {'G': 4},
  'F': {'G': 1},
  'G': {},
};

num heuristic(String node, String goal) =>
  node == goal ? 0 : 1; // Simple heuristic

final path = aStar(graph, 'A', 'G', heuristic);
// Result: ['A', 'B', 'D', 'G'] with cost 8

Classes

AStarNode<T>
Represents a node in the A* search with its f-score (g + h)
AStarResult<T>
A* with path cost calculation
PriorityQueue<T>
Simple priority queue implementation for A* algorithm

Functions

aStar<T>(Map<T, Map<T, num>> graph, T start, T goal, num heuristic(T node, T goal), {int maxIterations = 10000}) → List<T>
A* pathfinding algorithm implementation
aStarWithCost<T>(Map<T, Map<T, num>> graph, T start, T goal, num heuristic(T node, T goal), {int maxIterations = 10000}) → AStarResult<T>