When you want to find the fastest way to get somewhere—like navigating in a video game or on Google Maps—you need an algorithm that’s both smart and fast. That’s where A* comes in!

A* (pronounced “A Star”) is a graph search algorithm that finds the shortest path to a goal while also considering which paths seem more promising. It’s like combining the brains of Dijkstra’s Algorithm with the instincts of guessing where the finish line might be!

We already explored Dijkstra’s Algorithm, which guarantees the shortest path by exploring everything equally. A* improves on that by using a heuristic to prioritize better options first.

How A* Works

A* calculates two things for each point:

  • g(n): The actual cost to reach the point from the start.
  • h(n): An estimate (heuristic) of the cost to get from that point to the goal.

It adds them together:

f(n) = g(n) + h(n)

The path with the lowest f(n) is explored first!

Full Working Example: A* in C#

Here’s a simple, working A* example on a graph:

using System;
using System.Collections.Generic;
using System.Linq;

class Node
{
    public string Name;
    public List<(Node, int)> Neighbors = new List<(Node, int)>();
    public float G = float.MaxValue;
    public float H = 0;
    public float F => G + H;
    public Node Parent = null;

    public Node(string name)
    {
        Name = name;
    }
}

class AStar
{
    static float Heuristic(Node a, Node b)
    {
        // Simple heuristic: pretend it's always 0 (works like Dijkstra).
        return 0;
    }

    public static List<Node> FindPath(Node start, Node goal)
    {
        var openSet = new List<Node> { start };
        start.G = 0;
        start.H = Heuristic(start, goal);

        while (openSet.Count > 0)
        {
            var current = openSet.OrderBy(n => n.F).First();

            if (current == goal)
            {
                var path = new List<Node>();
                while (current != null)
                {
                    path.Add(current);
                    current = current.Parent;
                }
                path.Reverse();
                return path;
            }

            openSet.Remove(current);

            foreach (var (neighbor, cost) in current.Neighbors)
            {
                float tentativeG = current.G + cost;
                if (tentativeG < neighbor.G)
                {
                    neighbor.Parent = current;
                    neighbor.G = tentativeG;
                    neighbor.H = Heuristic(neighbor, goal);
                    if (!openSet.Contains(neighbor))
                        openSet.Add(neighbor);
                }
            }
        }

        return null; // No path found
    }
}

class Program
{
    static void Main()
    {
        var A = new Node("A");
        var B = new Node("B");
        var C = new Node("C");
        var D = new Node("D");
        var E = new Node("E");

        A.Neighbors.Add((B, 1));
        A.Neighbors.Add((C, 4));
        B.Neighbors.Add((C, 2));
        B.Neighbors.Add((D, 5));
        C.Neighbors.Add((D, 1));
        D.Neighbors.Add((E, 3));

        var path = AStar.FindPath(A, E);

        if (path != null)
        {
            Console.WriteLine("Path found:");
            foreach (var node in path)
                Console.Write(node.Name + " ");
        }
        else
        {
            Console.WriteLine("No path found.");
        }
    }
}

In this simple graph:

  • A connects to B (1) and C (4)
  • B connects to C (2) and D (5)
  • C connects to D (1)
  • D connects to E (3)

The A* search will find the fastest path from A to E.

Where is A* Used?

  • Video Games: Making characters move intelligently around obstacles.
  • GPS Systems: Finding the quickest route to your destination.
  • Robotics: Helping robots find paths around a room.
  • Network Routing: Finding efficient data paths across the internet.

Why A* is Powerful

  • Faster than Dijkstra when you have a good heuristic.
  • Flexible: You can tweak the heuristic for different needs (speed vs. accuracy).
  • Guaranteed Optimal if the heuristic never overestimates the true cost.

Final Thoughts

A* is one of the most important search algorithms in computer science because it strikes the perfect balance between speed and accuracy. Understanding how it works is a huge step toward mastering smart problem-solving techniques!

Next up: Recusrion and Divide & Conquer!