Shortest Path in an Undirected Graph

shriyanshi24jindal

Mar 29th, 2026

306

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 18.02 KB | None | 0 0

copy raw download clone embed print report

class iPair{
int first, second;
public iPair(int first, int second)
{
this.first = first;
this.second = second;
}
}
class Pair
{
int distance, node;
public Pair(int distance, int node)
{
this.distance = distance;
this.node = node;
}
}
class Solution {
public List<Integer> shortestPath(int n, int m, int edges[][]) {
// Step-1 create an adjacency list
ArrayList<ArrayList<iPair>> adj = new ArrayList<>();
for(int i=0;i<=n;i++)
{
adj.add(new ArrayList<iPair>());
}
for(int[] edge : edges)
{
int u = edge[0];
int v = edge[1];
int w = edge[2];
adj.get(u).add(new iPair(v,w));
adj.get(v).add(new iPair(u, w));
}
// Step-2 Create a distance array and parent node array
int[] distance = new int[n+1];
int[] parent = new int[n+1];
for(int i=0;i<=n;i++)
{
distance[i] = (int)1e9;
parent[i] = i;
}
distance[1] = 0;
// Step-3 Store the nodes into MIN-HEAP accoriding to node's weight
PriorityQueue<Pair> pq = new PriorityQueue<Pair>((x,y) -> Integer.compare(x.distance, y.distance));
pq.add(new Pair(0, 1));
// Step-4 Traverse the nodes present in min-heap
while(pq.size()!=0)
{
Pair pair = pq.poll();
int currentNode = pair.node;
int currentDist = pair.distance;
for(iPair neighbour : adj.get(currentNode))
{
int adjNode = neighbour.first;
int weight = neighbour.second;
if(distance[adjNode] > (currentDist + weight))
{
distance[adjNode] = currentDist + weight;
pq.add(new Pair(distance[adjNode], adjNode));
parent[adjNode] = currentNode;
}
}
}
List<Integer> arr = new ArrayList<>();
if(distance[n] == 1e9)
{
arr.add(-1);
return arr;
}
// Backtrack from destination to source
int node = n;
// Use the parent[] array to trace back the path
/**
* If path is:
1 → 2 → 4 → 5
Then:
parent[5] = 4
parent[4] = 2
parent[2] = 1
parent[1] = 1
Loop will:
add 5
add 4
add 2
(stop at 1 because parent[1] == 1)
**/
while(parent[node] != node)
{
arr.add(node);
node = parent[node];
}
// Because the loop stops before adding node 1, we add it explicitly.
arr.add(1);
// Add total distance
arr.add(distance[n]);
Collections.reverse(arr);
return arr;
}
}

RAW Paste Data Copied

class iPair{
    int first, second;
    public iPair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}

class Pair 
{
    int distance, node;
    public Pair(int distance, int node)
    {
        this.distance = distance;
        this.node = node;
    }
}

class Solution {
    public List<Integer> shortestPath(int n, int m, int edges[][]) {
        
        // Step-1 create an adjacency list
        ArrayList<ArrayList<iPair>> adj = new ArrayList<>();
        for(int i=0;i<=n;i++)
        {
            adj.add(new ArrayList<iPair>());
        }
        
        for(int[] edge : edges)
        {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            adj.get(u).add(new iPair(v,w));
            adj.get(v).add(new iPair(u, w));
        }
        
        // Step-2 Create a distance array and parent node array
        int[] distance = new int[n+1];
        int[] parent = new int[n+1];
        for(int i=0;i<=n;i++)
        {
            distance[i] = (int)1e9;
            parent[i] = i;
        }
        distance[1] = 0;
        
        // Step-3 Store the nodes into MIN-HEAP accoriding to node's weight
        PriorityQueue<Pair> pq = new PriorityQueue<Pair>((x,y) -> Integer.compare(x.distance, y.distance));
        pq.add(new Pair(0, 1));
        
        // Step-4 Traverse the nodes present in min-heap
        while(pq.size()!=0)
        {
            Pair pair = pq.poll();
            int currentNode = pair.node;
            int currentDist = pair.distance;
            
            for(iPair neighbour : adj.get(currentNode))
            {
                int adjNode = neighbour.first;
                int weight = neighbour.second;
                
                if(distance[adjNode] > (currentDist + weight))
                {
                    distance[adjNode] = currentDist + weight;
                    pq.add(new Pair(distance[adjNode], adjNode));
                    parent[adjNode] = currentNode;
                }
            }
        }
        
        List<Integer> arr = new ArrayList<>();
        if(distance[n] == 1e9)
        {
            arr.add(-1);
            return arr;
        }
        
        // Backtrack from destination to source
        int node = n;
        // Use the parent[] array to trace back the path
        /**
         * If path is:
            1 → 2 → 4 → 5
            
            Then:
            parent[5] = 4
            parent[4] = 2
            parent[2] = 1
            parent[1] = 1
            
            Loop will:
            add 5
            add 4
            add 2
            (stop at 1 because parent[1] == 1)
         **/
        while(parent[node] != node)
        {
            arr.add(node);
            node = parent[node];
        }
        // Because the loop stops before adding node 1, we add it explicitly.
        arr.add(1);
        // Add total distance
        arr.add(distance[n]);
        
        Collections.reverse(arr);
        return arr;
    }
}