The most awaited problem “Find the shortest path in a directed acyclic graph” 2D array
Introduction:
Most often interview questions I’ll try to explain more understandably as much as I can thanks for your support let’s dive into the question I don’t want to intimidate you guys easy peasy they are given directed acyclic graph (DAG) which means there is one graph without cycle they are clearly mentioned our task is to find the shortest path from SRC(0) vertex to all the vertices and if it is impossible to reach any vertex, then return -1 for that vertex :)
Question Decoding:
Comes to the question given a DAG with N vertices (Nodes) from 0 to N — 1 and a 2D integer array each array contains 3 lengths of the data [0, 1, 2] where there is a directed, edge from i[0] — →0 to i[1] — →1 which means the 0th node connected with a node of 1 okay what about i[2] just wait I’ll tell you what it is so far we’ve seen just there is two connected with edges who comes before and next that’s all with the edges we can’t find the shortest path so the question additionally gives the distance (weights) of the edges okay that are i[2] index okay if one line example is 0 — — → 1 the edges weight is 2 okay the source node always src(0).so far we’ve seen Kahn’s topo something this one also similar but different algorithm no worry easy peasy
Visual Question Decoding:
Making adjList with edges:
First, create an array in C++ vector because we want to store the adjacent node so far we’ve just stored the adjNode but here we need to store a pair of the adjacent nodes which means along with the weight or distance of the particular adjacent node one more thing all the indexes are denoting the where do start inside of pair 0th node denoting the particular adjacent the 1st index is that particular weight of the edge okay then write a nested loop
let adj = new Array(n).fill(null).map(() => []);
//// adj ---> just assume looks like [[1,2],[3,5],[4,6],[8,9]]
//// 0th adjnode is 1 and particular weight is 2
//// 1st adjNode is 3 and particular weight is 5
//// 2nd adjNode is 4 and particular weight is 6
for (let i = 0; i < m; i++) {
let U = edges[i][0]; // start node
let V = edges[i][1]; // just assume destination adjNode
let W = edges[i][2]; // that particular edges weight
adj[U].push([V, W]); // simply push into the adjList array
}
// // console.log(adj);Core of the problem:
The question strictly says the source node is always 0 might a question arise what if the interviewer assigned another source node don’t panic whatever source node first make an adjList with edges then make Topo order for the particular adjList then you can easily find who is your source node the why Topo order Marudhu — → In the context of finding the shortest path in a directed acyclic graph (DAG), performing a topological sort can indeed help identify a suitable starting point or source node for the shortest path algorithm and Such vertices are guaranteed to be reachable from the beginning and won’t require unnecessary traversals of unreachable vertices if you don’t know how to make a Topo order please please go back read our first blog that will really help you make topo order any given adjList okay.
A small introduction about topo making:
When topo making you can do it with two approaches 1) DFS, and 2) BFS in this DAG we are going to use DFS.
1) Create a visited array edges length filled with 0 or false
2) We need one DS Stack for storing and tracking all the adjNodes
3) Then start a loop to adjList length start with 0 on the index and find who the adjNode of the 0th index pushes into the stack if anyone has leads to the particular node of the adjNode till push the adjNode becomes 0 that’s called DFS keep digging guys
4) Stack is LIFO okay who are in the top of the stack that’s our source node and extracts the source node from the stack find the distance of the node to the destination I’ll tell you in upcoming space.
Find the distance from the source node:
Processing:
- First, find the adjList with the edges
- After getting the adjList make the topo-order with the powerful technique DFS
- I hope your stack has some set of lists don’t forget to pop because LIFO
- Finally, jump to find the distance of each nodes simply write a while loop till the stack becomes 0 in JS has the pop method extract the node from the top of the stack pair of 0th node is adjacent node 1st value is a distance of the edges so calculate the edges fill with particular adjacent node before fill the distance just make sure is better or not if better just fill with the distance simple….. :)
Code Showcase:
class Solution {
//// second
topoDfs(node, visited, stack, adjList) {
visited[node] = true;
for (let neighbor of adjList[node]) {
let joiningV = neighbor[0];
if (!visited[joiningV]) {
this.topoDfs(joiningV, visited, stack, adjList);
}
}
stack.push(node);
}
Graph(m, n, edges) {
//// first
let adj = new Array(n).fill(null).map(() => []);
// console.log(adj);
for (let i = 0; i < m; i++) {
let U = edges[i][0];
let V = edges[i][1];
let W = edges[i][2];
adj[U].push([V, W]);
}
// console.log(adj, "adjList");
let visited = new Array(n).fill(false);
let stack = [];
for (let i = 0; i < n; i++) {
if (!visited[i]) {
this.topoDfs(i, visited, stack, adj);
}
}
// console.log(stack, "stack");
//// Last process don't see at first
let distance = new Array(n).fill(Infinity);
distance[0] = 0;
while (stack.length > 0) {
let topNode = stack.pop();
// console.log(topNode, "topNode");
for (let adjacent of adj[topNode]) {
let v = adjacent[0];
let weight = adjacent[1];
if (distance[topNode] + weight < distance[v]) {
distance[v] = distance[topNode] + weight;
}
}
}
return distance;
}
}
let edges = [ //// edges edges edges don't assume adjLis... :)
[0, 1, 2],
[0, 4, 1],
[4, 5, 4],
[4, 2, 2],
[1, 2, 3],
[2, 3, 6],
[5, 3, 1],
];
let m = edges.length;
let n = 6;
let data = new Solution();
let output = data.Graph(m, n, edges);
console.log(output, "your shortest path");Time to say bye-bye:
we’ve done a blog on finding the shortest path in a directed acyclic graph thanks for sticking together so far your support really means everything to me just if you have enjoyed the content please consider hitting the follow button and don’t forget to hit the applaud button as well thanks again to everyone who has supported me along the journey will see at the next blog :)
