Shortest Path in Undirected Graph

shriyanshi24jindal

Mar 29th, 2026

Never

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

Java 11.20 KB | None | 0 0

copy raw download clone embed print report

class Pair
{
int first;
int second;
Pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
class Solution {
public int[] shortestPath(int V, int[][] edges, int src) {
// Step-1 create a adjancency list
ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
for(int i=0; i<V; i++)
{
adj.add(new ArrayList<>());
}
for(int[] edge : edges)
{
int u = edge[0];
int v = edge[1];
adj.get(u).add(v);
adj.get(v).add(u);
}
// Step-2 Traverse through nodes starting from source node
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(src, 0));
// Step-3 Create a distance matrix which will store shortest distance for each node
int[] distance = new int[V];
Arrays.fill(distance, Integer.MAX_VALUE);
distance[src ] = 0;
// Step-4 Traverse through nodes
while(!q.isEmpty())
{
Pair pair = q.poll();
int node = pair.first;
int dist = pair.second;
// traverse through neighbour nodes
for(int u : adj.get(node))
{
// if distance of neighbour node is greater than the current distance+1 then update it
if(distance[u] > dist+1)
{
distance[u] = dist+1;
q.add(new Pair(u, dist+1));
}
}
}
for(int i=0; i<V; i++)
{
// If a vertex is not reachable from the source, return -1 for that vertex
if(distance[i] == Integer.MAX_VALUE)
distance[i] = -1;
}
return distance;
}
}

RAW Paste Data Copied

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

class Solution {
    public int[] shortestPath(int V, int[][] edges, int src) {
        // Step-1 create a adjancency list
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for(int i=0; i<V; i++)
        {
            adj.add(new ArrayList<>());
        }
        
        for(int[] edge : edges)
        {
            int u = edge[0];
            int v = edge[1];
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
        
        // Step-2 Traverse through nodes starting from source node
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(src, 0));
        
        // Step-3 Create a distance matrix which will store shortest distance for each node
        int[] distance = new int[V];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[src ] = 0;
        
        // Step-4 Traverse through nodes
        while(!q.isEmpty())
        {
            Pair pair = q.poll();
            int node = pair.first;
            int dist = pair.second;
            
            // traverse through neighbour nodes
            for(int u : adj.get(node))
            {
                // if distance of neighbour node is greater than the current distance+1 then update it
                if(distance[u] > dist+1)
                {
                    distance[u] = dist+1;
                    q.add(new Pair(u, dist+1));
                }
            }
        }
        
        for(int i=0; i<V; i++)
        {
            // If a vertex is not reachable from the source, return -1 for that vertex
            if(distance[i] == Integer.MAX_VALUE)
                distance[i] = -1;
        }
        return distance;
    }
}