Shortest path in a Directed Acyclic graph from source to all other nodes can be achieved using Topological sorting followed by breadth first traversal of the graph (We will required stack to store the topological sorting and on the stack we will do breadth first search to get the shortest distance.
The reason of using topo sort is simple, we save a lot of time by starting from the start point, instead of starting from any random point. Since we know via topo sort we get to know the starting point, hence it becomes optimal to use topo sort!)
Solution: Time complexity is 2*O(n+e) where n is nodes and e is edges 2 because o(n+e) for topo sort and o(n+e) for breadth first search
Space complexity is o(n) for visited, o(n) for distance, o(n) for stack space of topo sort and o(n) for Stack<Integer> = 4*o(n)
private int[] shortestPath(ArrayList<ArrayList<Pair>> adj,int N){
// here pair will store edge weight between two nodes having and edge
//example if u and v have and edge with weight 3, => u.add(new Pair(v,5)); like this.
// first we will have to identify the source or the starting point in the graph
// so that distance of traversing all other nodes will be smaller from this node.
// for this we will use topo sorting
Stack<Integer> stack = new Stack<>();
int visited[] = new int[N];
for(int i =0;i<N;i++){
if(visited[i] ==0){
dfs(i,adj,visited,stack);
}
}
//now the stack will have topo sorted nodes of the graph.
//now we will do breadth first search for getting shortest path from source to
// all the other nodes in the graph.
int distance[] = new int[N];
// source node will be
int source = stack.peek();
Arrays.fill(distance,Integer.MAX_VALUE);// distance of all other nodes from the source will be infinite initially.
distance[source] = 0;// source distance will be zero
while(!stack.isEmpty()){
Integer i = stack.pop();
if(distance[i]!=Integer.MAX_VALUE){ // just to make sure that that current node is reachable
for(Pair pair : adj.get(i)){
if(distance[pair.getKey()]> distance[i]+ pair.getValue()){
distance[pair.getKey()] = distance[i] + pair.getValue();
}
}
}
}
return distance; /// for any node if the distance comes as Integer.MAX_VALUE then that node is not reachable from the source node.
}
public void dfs(int node, ArrayList<ArrayList<Pair>> adj, int[] visited,Stack<Integer> stack){
visited[node] = 1;
for(Pair i : adj.get(node)){
if(visited[i.getKey()] ==0) dfs(i.getKey(),adj,visited,stack);
}
stack.push(node);
}
class Pair{
private int key;
private int value;
public Pair(){
super();
}
public Pair(int i,int j){
this.key = i;
this.value =j;
}
public int getKey(){
return this.key;
}
public int getValue(){
return this.getValue();
}
}
Top comments (0)