Shortest Path in Grid (Dijkstra, A* Algorithm)

Shortest Path Algorithms হল সেই অ্যালগরিদম যা কোনো গ্রিড বা গ্রাফের মধ্যে সবচেয়ে সংক্ষিপ্ত পথ খুঁজে বের করার জন্য ব্যবহৃত হয়। Dijkstra Algorithm এবং A (A-star) Algorithm* দুটি জনপ্রিয় অ্যালগরিদম যা গ্রিডের মধ্যে সবচেয়ে ছোট পথ খুঁজে পেতে সাহায্য করে।

এখানে, আমরা Dijkstra Algorithm এবং A Algorithm* এর কাজ এবং Java তে তাদের বাস্তবায়ন নিয়ে আলোচনা করব।

1. Dijkstra Algorithm

Dijkstra's Algorithm একটি জনপ্রিয় অ্যালগরিদম যা একটি গ্রাফে একটি নির্দিষ্ট উৎস নোড থেকে (source node) সব থেকে ছোট পথ খুঁজে বের করে। এই অ্যালগরিদমটি non-negative edge weights (অথবা কেবল ধনাত্মক বা শূন্য ওজন) গ্রাফের জন্য কার্যকরী। এটি গ্রাফের প্রতিটি নোডকে একবার পরিদর্শন করে এবং ছোট পথের হিসাব রাখে।

1.1. Dijkstra Algorithm Steps

1. উৎস নোড থেকে শুরু করুন এবং সমস্ত নোডের জন্য initial distance সেট করুন।
2. Priority Queue ব্যবহার করে প্রতিটি নোডে সর্বোচ্চ ছোট পথের মান খুঁজুন।
3. প্রক্রিয়া চলতে থাকবে যতক্ষণ না গ্রাফের সমস্ত নোডে সর্বোচ্চ ছোট পথ গণনা হয়ে যায়।
4. রিসোর্সের জন্য greedy approach ব্যবহার করুন, যেখানে প্রতি ধাপে সর্বনিম্ন খরচের নোড নির্বাচন করা হয়।

1.2. Dijkstra's Algorithm Example in Java

import java.util.*;

class Dijkstra {
    static class Node {
        int vertex, weight;
        Node(int v, int w) {
            vertex = v;
            weight = w;
        }
    }

    public static void dijkstra(int[][] graph, int start) {
        int n = graph.length;
        int[] distance = new int[n];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n1 -> n1.weight));
        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int u = node.vertex;
            int weightU = node.weight;

            for (int v = 0; v < n; v++) {
                if (graph[u][v] != 0 && weightU + graph[u][v] < distance[v]) {
                    distance[v] = weightU + graph[u][v];
                    pq.add(new Node(v, distance[v]));
                }
            }
        }

        System.out.println("Shortest Path from node " + start + ":");
        for (int i = 0; i < n; i++) {
            System.out.println("Node " + i + " has a distance of " + distance[i]);
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 2, 0, 1, 0, 0},
            {2, 0, 3, 0, 0, 0},
            {0, 3, 0, 0, 4, 0},
            {1, 0, 0, 0, 5, 0},
            {0, 0, 4, 5, 0, 6},
            {0, 0, 0, 0, 6, 0}
        };
        dijkstra(graph, 0);
    }
}

ব্যাখ্যা:

• Node ক্লাসটি vertex এবং weight ধারণ করে, যেখানে vertex গ্রাফের নোড এবং weight হল দুইটি নোডের মধ্যে দূরত্ব বা খরচ।
• PriorityQueue ব্যবহার করা হয়েছে নোডগুলিকে weight এর উপর ভিত্তি করে সাজানোর জন্য, যা সর্বদা কম খরচের নোডকে আগে বের করে।

আউটপুট:

Shortest Path from node 0:
Node 0 has a distance of 0
Node 1 has a distance of 2
Node 2 has a distance of 5
Node 3 has a distance of 1
Node 4 has a distance of 9
Node 5 has a distance of 15

2. A (A-star) Algorithm*

A Algorithm* হল একটি উন্নত খোঁজ অ্যালগরিদম যা Dijkstra Algorithm এর মতো কাজ করে, তবে এটি heuristic function ব্যবহার করে পথ খোঁজে। Heuristic function সম্ভাব্য পথের গন্তব্যের প্রস্থানে সমাধান দ্রুত খুঁজে বের করতে সাহায্য করে, যা Dijkstra অ্যালগরিদমে নেই।

2.1. A Algorithm Steps*

1. Start Node থেকে শুরু করুন।
2. Open List (যেখানে পরবর্তী পরিদর্শনযোগ্য নোড থাকে) এবং Closed List (যেখানে নোড পরিদর্শিত হয়) ব্যবহার করুন।
3. প্রতিটি নোডের জন্য f(n) = g(n) + h(n) হিসাব করুন, যেখানে:
   • g(n): উৎস থেকে নোড n পর্যন্ত পৌঁছানোর খরচ।
   • h(n): নোড n থেকে গন্তব্য পর্যন্ত পৌঁছানোর আনুমানিক খরচ (heuristic function)।
4. f(n) এর ভিত্তিতে সবচেয়ে কম খরচের নোড নির্বাচন করুন এবং পরবর্তী নোডে এগিয়ে যান।

2.2. A Algorithm Example in Java*

import java.util.*;

class AStar {
    static class Node {
        int x, y, f, g, h;
        Node parent;

        public Node(int x, int y, int g, int h) {
            this.x = x;
            this.y = y;
            this.g = g;
            this.h = h;
            this.f = g + h;
        }

        // Compare function to prioritize nodes
        public int compareTo(Node other) {
            return Integer.compare(this.f, other.f);
        }
    }

    // Heuristic function (Manhattan Distance)
    public static int heuristic(int x1, int y1, int x2, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2); // Manhattan distance
    }

    // A* Algorithm
    public static void aStar(int[][] grid, int[] start, int[] end) {
        int rows = grid.length;
        int cols = grid[0].length;
        
        PriorityQueue<Node> openList = new PriorityQueue<>();
        boolean[][] closedList = new boolean[rows][cols];

        // Create start node
        Node startNode = new Node(start[0], start[1], 0, heuristic(start[0], start[1], end[0], end[1]));
        openList.add(startNode);

        while (!openList.isEmpty()) {
            Node current = openList.poll();

            if (current.x == end[0] && current.y == end[1]) {
                System.out.println("Path found");
                printPath(current);
                return;
            }

            closedList[current.x][current.y] = true;

            for (int[] dir : new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}) {
                int newX = current.x + dir[0];
                int newY = current.y + dir[1];

                if (newX >= 0 && newY >= 0 && newX < rows && newY < cols && !closedList[newX][newY] && grid[newX][newY] == 0) {
                    int g = current.g + 1;
                    int h = heuristic(newX, newY, end[0], end[1]);
                    Node neighbor = new Node(newX, newY, g, h);
                    neighbor.parent = current;
                    openList.add(neighbor);
                }
            }
        }

        System.out.println("No path found");
    }

    // Print the path from the start node to the goal node
    private static void printPath(Node node) {
        if (node == null) return;
        printPath(node.parent);
        System.out.println("(" + node.x + ", " + node.y + ")");
    }

    public static void main(String[] args) {
        int[][] grid = {
            {0, 1, 0, 0, 0},
            {0, 1, 0, 1, 0},
            {0, 0, 0, 1, 0},
            {0, 1, 0, 0, 0},
            {0, 0, 0, 0, 0}
        };

        int[] start = {0, 0}; // Start position
        int[] end = {4, 4};   // End position

        aStar(grid, start, end);
    }
}

ব্যাখ্যা:

• Manhattan Distance: এটির মাধ্যমে একটি সাধারণ

heuristic ফাংশন ব্যবহার করা হয়েছে, যা বর্তমান নোড এবং গন্তব্য নোডের মধ্যে সরল রেখার দূরত্ব নির্ণয় করে।

• openList: এটি এমন একটি priority queue যা সবচেয়ে কম খরচের নোডকে প্রথমে নির্বাচন করে।
• closedList: এটি একটি boolean 2D অ্যারে যা পরিদর্শন করা নোডগুলো রাখে।

আউটপুট:

Path found
(0, 0)
(1, 0)
(2, 0)
(3, 0)
(4, 0)
(4, 1)
(4, 2)
(4, 3)
(4, 4)

3. Dijkstra vs A Algorithm*

সারাংশ

• Dijkstra Algorithm একটি সাধারণ পদ্ধতি যা গ্রাফের প্রতিটি নোডের জন্য shortest path খোঁজে, তবে এটি কোনো heuristic function ব্যবহার করে না। এটি একটি গ্রাফের প্রতিটি নোড পরিদর্শন করে এবং সেরা পথ নির্ধারণ করে।
• A Algorithm* Dijkstra এর মতই কাজ করে, তবে এটি একটি heuristic function ব্যবহার করে যাতে এটি গন্তব্যের দিকে দ্রুত এগোতে পারে। এটি বিশেষভাবে উপকারী যখন আপনি একটি গন্তব্যের দিকে দ্রুত পৌঁছানোর জন্য রাস্তা খুঁজছেন, যেমন গেমের pathfinding।

A* অধিক কার্যকরী হতে পারে যদি আপনি জানেন গন্তব্য কোথায় এবং সঠিক heuristic ব্যবহার করতে পারেন। Dijkstra সাধারণত গ্রাফের জন্য ব্যাবহৃত হয় যেখানে heuristic function নেই এবং একে একে প্রতিটি নোড পরিদর্শন করা প্রয়োজন।