min path edge

/*
    Time Complexity : O(N + M)      
    Space Complexity : O(N + M)

    where N is the number of nodes and M is number of edges.
*/

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Collections;

public class Solution 
{
    public static LinkedList<Integer> shortestPath(int[][] edges, int n, int m, int s, int t) 
    {    
        // Storing the graph in an adjacency list.
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>(n + 1);

        for (int i = 0; i <= n; i++) 
        {
            adj.add(new ArrayList<>());
        }

        // Building the adjacency list from the edge list.
        for (int i = 0; i < m; i++) 
        {
            int x = edges[i][0];
            int y = edges[i][1];
            adj.get(x).add(y);
            adj.get(y).add(x);
        }


        // Declaring visited and parent arrays.
        int[] visited = new int[n + 1];
        int[] parent = new int[n + 1];

        for (int i = 1; i <= n; i++) 
        {
            visited[i] = 0;
            parent[i] = -1;
        }

        // Starting BFS from node S.
        LinkedList<Integer> q = new LinkedList<>();
        visited[s] = 1;
        parent[s] = -1;
        q.add(s);

        // BFS with early exit when we reach target node T.
        while (!q.isEmpty()) 
        {
            int currentNode = q.remove();

            for (int neighbor : adj.get(currentNode)) 
            {
                if (visited[neighbor] == 0) 
                {
                    visited[neighbor] = 1;
                    parent[neighbor] = currentNode;
                    q.add(neighbor);
                    // Early exit if we reached target.
                    if (neighbor == t) {
                        break;
                    }
                }
            }
        }

        // Reconstructing the shortest path from S to T.
        LinkedList<Integer> path = new LinkedList<>();
        int currentNode = t;
        path.add(currentNode);

        while (parent[currentNode] != -1) 
        {
            currentNode = parent[currentNode];
            path.add(currentNode);
        }

        // Reversing the path since we built it from T to S.
        Collections.reverse(path);
        return path;
    }
}