A* Algorithm: Combining Speed and Accuracy

A* Star Algorithm helps us find the shortest path in a graph, often faster than traditional algorithms like BFS or Dijkstra’s Algorithm. Both BFS and Dijkstra’s Algorithm have their strengths, but they can be slow, especially when dealing with complex graphs.

The Need for Speed and Accuracy

The problem with BFS is its lack of intelligence. It explores every node without considering their relevance to the destination. Dijkstra’s Algorithm is an improvement but can still visit unnecessary nodes.

When dealing with massive graphs, like the ones Google Maps handles, speed becomes crucial. This is where A* Algorithm shines.

How A* Algorithm Works

A* Algorithm is similar to Dijkstra’s but adds a touch of intelligence. It judges whether a node is close to the destination, making it faster.

Formula:

Cost = Distance(start_node, current_node) + Heuristic(current_node, destination_node)

Cost: Total cost of the current node.
Distance(start_node, current_node): Actual distance between start_node and current_node.
Heuristic(current_node, destination_node): Estimated distance from current_node to destination_node.

Heuristic Function

The heuristic function provides an approximate distance from point A to point B. One common heuristic is Euclidean Distance:

h(n) = sqrt((x₂ - x₁)² + (y₂ - y₁)²)

Java Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82


public class Main {
    public static void main(String[] args) {
        AStar algo = new AStar();
        // 0 - accessible, 1 - obstacle
        int[][] graph1 = {
            {0, 0, 0, 1, 0},
            {0, 0, 0, 1, 0},
            {0, 1, 0, 1, 0},
            {0, 1, 0, 1, 0},
            {0, 1, 0, 0, 0}
        };
        int shortestDistance1 = algo.ETA(graph1, 0, 0, 4, 4);
        System.out.println("Shortest Distance: " + shortestDistance1);
    }
}

class AStar {
    class Node {
        int x, y;
        int cost; // g(n) + h(n)
        int dist; // g(n)
        List<String> list;
        public Node(int x, int y, int cost, int dist, List<String> list) {
            this.x = x;
            this.y = y;
            this.cost = cost;
            this.dist = dist;
            this.list = list;
        }
    }
    
    private int[] ROWS = {0, 1, 0, -1, 1, 1, -1, -1};
    private int[] COLS = {1, 0, -1, 0, 1, -1, 1, -1};
    
    public int ETA(int[][] graph, int s1, int s2, int d1, int d2) {
        // rows, cols
        int n = graph.length, m = graph[0].length;
        
        // obstacle is present at source or destination
        if(graph[s1][s2] == 1 || graph[d1][d2] == 1) return -1;
        
        // node with less cost gets preference
        PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> x.cost - y.cost);
        List<String> list = new ArrayList<>();
        list.add(s1 + "|" + s2);
        pq.add(new Node(s1, s2, 0, 0, list));
        Set<String> visitedNodes = new HashSet<>();
        visitedNodes.add(s1 + "|" + s2);
        while(!pq.isEmpty()) {
            Node curr = pq.poll();
            int c1 = curr.x, c2 = curr.y, co = curr.cost;
            if(c1 == d1 && c2 == d2) {
                System.out.println(curr.list);
                return curr.dist;
            }
            
            // find the neighbours - assuming we can go in eight directions
            for(int dir = 0; dir < 8; dir++) {
                int nextRow = c1 + ROWS[dir];
                int nextCol = c2 + COLS[dir];
                
                // next node must be valid node
                if(nextRow < 0 || nextCol < 0 || nextRow >= n || nextCol >= m || graph[nextRow][nextCol] == 1 || visitedNodes.contains(nextRow + "|" + nextCol)) continue;
                
                // considering 1 as distance between any two nodes
                int totalDist = curr.dist + 1;
                
                int cost = totalDist + heuristic(nextRow, nextCol, d1, d2);
                List<String> newList = new ArrayList<>(curr.list);
                newList.add(nextRow + "|" + nextCol);
                pq.add(new Node(nextRow, nextCol, cost, totalDist, newList));
                visitedNodes.add(nextRow + "|" + nextCol);
            }
        }
        // no path found
        return -1;
    }
    
    private int heuristic(int s1, int s2, int d1, int d2) {
         return (int)(Math.sqrt(Math.pow(d1-s1, 2) + Math.pow(d2-s2, 2)));
    }
}

This is very similar to Dijkstra, but what really adds intelligence to this algorithm is Heuristic function.

Let’s see the difference:

Dijkstra’s Algorithm	A* Algorithm

Resources:

A* Algorithm