Shortest path in Directed Acyclic Graph

shriyanshi24jindal

Mar 29th, 2026

Never

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

Java 16.42 KB | None | 0 0

copy raw download clone embed print report

// User function Template for Java
class Pair
{
int vertex;
int weight;
Pair(int vertex, int weight)
{
this.vertex = vertex;
this.weight = weight;
}
}
class Solution {
/**
* 1. Create a adjancency list, for each node store {vertex, weight} as neighbour.
* 2. Find the topological sort of given graph and store it in stack
* 3. Create a distance array, assign all values as Int_MAX except source node will have distance as 0.
* 4. Run a loop until stack becomes empty
* - Relax the edges
* - For every neighbour check if distance[neighbour] > distance[currentNode] + weight
* - if yes, then update the distance of neighbour
* 5. if any vertex is unreachable then update distance as -1
* 6. Return the distance array
* */
public int[] shortestPath(int V, int E, int[][] edges) {
// Step-1 create a adjancency list
// We will store neighbour nodes as well as weight between the nodes
ArrayList<ArrayList<Pair>> adj = new ArrayList<>();
for(int i=0; i<V; i++)
{
adj.add(new ArrayList<Pair>());
}
for(int[] edge : edges)
{
int u = edge[0];
int v = edge[1];
int w = edge[2];
adj.get(u).add(new Pair(v, w));
}
// Step-2 Find the topological sort
Stack<Integer> st = new Stack<>();
boolean[] visited = new boolean[V];
for(int i=0; i<V; i++)
{
if(visited[i] == false)
{
topoSort(adj, visited, st, i);
}
}
// Step-3 define the distance array
int[] distance = new int[V];
Arrays.fill(distance, Integer.MAX_VALUE);
distance[0] = 0;
// Step-4 relax the edges
while(!st.isEmpty())
{
int node = st.pop();
for(Pair pair : adj.get(node))
{
int vertex = pair.vertex;
int weight = pair.weight;
// relax the edges
if(distance[node] != Integer.MAX_VALUE && (distance[vertex] > distance[node] + weight))
{
distance[vertex] = distance[node] + weight;
}
}
}
// Step-5 if vertex is unreachable then update distance as -1
for(int i=0;i<V;i++)
{
if(distance[i] == Integer.MAX_VALUE)
distance[i] = -1;
}
return distance;
}
public void topoSort(ArrayList<ArrayList<Pair>> adj, boolean[] visited, Stack<Integer> st, int node)
{
visited[node] = true;
// traversing neighbouring nodes
for(Pair p : adj.get(node))
{
int u = p.vertex;
if(visited[u] == false)
topoSort(adj,visited,st,u);
}
st.push(node);
}
}

RAW Paste Data Copied

// User function Template for Java
class Pair
{
    int vertex;
    int weight;
    Pair(int vertex, int weight)
    {
        this.vertex = vertex;
        this.weight = weight;
    }
}

class Solution {
    /**
     * 1. Create a adjancency list, for each node store {vertex, weight} as neighbour.
     * 2. Find the topological sort of given graph and store it in stack
     * 3. Create a distance array, assign all values as Int_MAX except source node will have distance as 0.
     * 4. Run a loop until stack becomes empty
     *    - Relax the edges
     *      - For every neighbour check if distance[neighbour] > distance[currentNode] + weight
     *      - if yes, then update the distance of neighbour
     * 5. if any vertex is unreachable then update distance as -1
     * 6. Return the distance array
     * */
    public int[] shortestPath(int V, int E, int[][] edges) {
        // Step-1 create a adjancency list
        // We will store neighbour nodes as well as weight between the nodes
        ArrayList<ArrayList<Pair>> adj = new ArrayList<>();
        for(int i=0; i<V; i++)
        {
            adj.add(new ArrayList<Pair>());
        }
        
        for(int[] edge : edges)
        {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            adj.get(u).add(new Pair(v, w));
        }
        
        // Step-2 Find the topological sort
        Stack<Integer> st = new Stack<>();
        boolean[] visited = new boolean[V];
        for(int i=0; i<V; i++)
        {
            if(visited[i] == false)
            {
                topoSort(adj, visited, st, i);
            }
        }
        
        // Step-3 define the distance array
        int[] distance = new int[V];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[0] = 0;
        
        // Step-4 relax the edges
        while(!st.isEmpty())
        {
            int node = st.pop();

for(Pair pair : adj.get(node))
            {
                int vertex = pair.vertex;
                int weight = pair.weight;
                
                // relax the edges
                if(distance[node] != Integer.MAX_VALUE && (distance[vertex] > distance[node] + weight))
                {
                    distance[vertex] = distance[node] + weight;
                }
            }
        }
        
        // Step-5 if vertex is unreachable then update distance as -1
        for(int i=0;i<V;i++)
        {
            if(distance[i] == Integer.MAX_VALUE)
                distance[i] = -1;
        }
        return distance;
    }
    
    
    public void topoSort(ArrayList<ArrayList<Pair>> adj, boolean[] visited, Stack<Integer> st, int node)
    {
        visited[node] = true;
        
        // traversing neighbouring nodes
        for(Pair p : adj.get(node))
        {
            int u = p.vertex;
            if(visited[u] == false)
                topoSort(adj,visited,st,u);
        }
        st.push(node);
    }
}