Network Delay Time | Leetcode
Vložit
- čas přidán 20. 09. 2020
- This video explains the network delay problem which is from leetcode 743 and it is a very commonly asked graph interview question.We can solve this problem by using 3 methods which are BFS, DFS and Dijkstra Algorithm.In this video, I have shown the intuition for solving using Dijkstra algorithm and Breadth First Search (BFS) algorithm.I have explained the dry run using BFS algorithm.Before explaining algorithm, I have also explained the intuition behind each algorithm.At the end of the video, I have also explained the CODE for the BFS algorithm.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithTECHDOSE
TELEGRAM Group LINK: t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
USEFUL LINK:-
Dijkstra algorithm: • Dijkstra algorithm | S...
Dijkstra algorithm Code implementation: • Dijkstra algorithm | C...
Breadth first search (BFS): • Breadth first search |...
Depth First Search (DFS): • Depth first search | D...
One question when we process node 5.
Why are we putting node 5 in q 2 times-> 5,6 and then 5,5
We can maintain
set of visited nodes
Q has only nodes (not distances)
Distance = array of all distances from S, initialized to 0,INf,INf...
While q:
Node = q.popleft()
For all neighbors of node:
If neighbor not in visited:
Visited.add(neighbor)
Q.append(neighbor)
dist[neighbor] = min (dist[neighbor], dist[node] + edgeweight
We may traverse edges multiple times. Example say node 5 had outgoing edge to node 7 with weight 10. We will process for 5,6 then again 5,5 and traverse 5-> 7 two times.
I understand what you are mentioning. You can take a map and simply just push the child nodes based on its level. This will allow each nodes to be pushed only once.
it also add extra 0(n ) space if we want to track which node is visited or not
amazing job buddy
@Tech Dose, isn't the time complexity O(V*E)?
Sir , I am eagerly waiting for DP course
It will come soon. Just making sure that graph is self sufficient for placement :)
Sir how time complexity is V+E? You are visiting nodes multiple times incase you find better distance I guess time complexity is V*E
Can you please explain why it's V*E?
Does this version of bfs replace dijkstra related problems?
I have the same question
Can u please provide solution and explanation for the below :
Write a program to find Largest 4 digits Prime Number whose Sum of Digits is also Prime.
1.Prime Number is any number that is divisible only by 1 and itself. Examples are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,........
2.Sum of Digits means sum of all the digits in that number. Example is number is 1234 then the sum of digits is 1+2+3+4=10
👍🙏
Are you writing this all with a mouse on a computer? Great video, how did you make this, are you using a stylus?
he's either using a graphic tablet or a phone/tab with a pen. if you notice closely in his other videos where his face is visible, he always looks down while changing the color of the pen, he wouldn't have to, had he been using just the mouse. LOL
When will the dp course starts?
After some more graph videos. Stay tuned :)
Do I need to learn semester subjects like digital logic, discrete structure engineering math etc for interview purpose? please help sir🙏
It's not very important. The most important thing is coding. Apart from that, theory depends on company. If you are sitting for banking company then DBMS is important. For network company, OS and Linux are important. For electronics company Digital Logic is important etc.
@@techdose4u for most of the product based company... what should I do?
Do just OS DBMS Linux (taught in sem). That should be enough. Some companies do ask Digital Logic but those are very few.
@@techdose4u ok sir thank you ❤️
Welcome
I am having trouble understanding why the time complexity of this problem is different from the one of Dijkstra?
Because I showed using BFS :)
@@techdose4u hmmm..thanks for the prompt response! is it related to one-directed or bi-directed graph?
you have explained "find the minimum time taken to reach the farthest node" in first 3-5 mins i have watched, so your example (4,1,1),(4,2,2),(2,3,3) ->ans is 5 but what if (4,1,6),(4,2,2),(2,3,3) is the graph according to your explanation it should be 5 but ans should be 6 , but signal should not have reached first node , so explanation is bit confusing......it should be the maximum of minimum time to reach each node , in that case signal would be reaching all nodes
XSuper good
Can u please make a video on word wrap problem sir??
I will try
This may not work when the graph has a cycle in it!
why? we only push to the queue if the value is small, for a back edge the value will be higher so it will be ignored right?
you didn't dealt with cycle case ? I think this is incomplete solution
Why haven't we used this method in the Dijkstra algorithm to reduce its time complexity from O(ElogV) to O(V+E)?
this will give wrong ans for cyclic ..so it is safe to use dijkstra algo..because u dont know if there is cycle or not.
this will work perfectly for non cyclic but dijkstra has the the advantage of handling cycle in graph
@@irrompible4588 Thank you for the clarification
@@irrompible4588 even though if we get a cycle at first time we just taking the minimum distance if the condition is true , from next time if we traverse in the same path means then, it will not add that into the queue why because, we already taken that distance so, bfs works fine if there is a cycle.
dial's algorithm
sir, i am from jadavpur university, and I want to know wether you also studied at jadavpur university?
Yes
@@techdose4u surya sir, really proud for me to have you as our alumni.
I am honored 😀
Why use dijktsra then since we can find shortest path using bfs?
Please read these: stackoverflow.com/questions/8379785/how-does-a-breadth-first-search-work-when-looking-for-shortest-path#:~:text=To%20find%20the%20shortest%20path,you%20find%20your%20destination%20Node.&text=However%2C%20if%20the%20graph%20is,of%20BFS%2C%20i.e.%20Dijkstra's%20algorithm.
www.freecodecamp.org/news/exploring-the-applications-and-limits-of-breadth-first-search-to-the-shortest-paths-in-a-weighted-1e7b28b3307/
Okay you can use bfs and can find the shortest path but the only condition is that In BFS, each edge must be having same weight then only we are able to apply Bfs.
If all the edges are not same/ or different , then we have to apply dijkstra algorithm for finding the shortest path.
@@exodus5948 but how is that applicable here? every edge has a different weight in the example shown in the video and still bfs is working? how?
@@anubhavaggarwal017have you find answer
Java Code with help of Dijkstra's Algorithm: gist.github.com/aman-5757/59121bccac300475db0df0d3915e6e38
In the official leetcode solution, BFS was used with time complexity of O(V+E). How come BFS is more optimal than dijkstra's approach which has time complexity of O(V + ElogV)?
BFS code will fail, when you have circular dependency in graph, like
[[1,2,1],[1,3,4],[3,4,2],[2,3,1],[3,2,1]]
4
1
As per test cases, this is valid test case.
Maintain the priority queue while inserting next items. And mark visit which has been processed. This will work for all cases including cyclic graphs.
It works completely fine even with the test case that you mentioned without any visited array just by using normal bfs. here we are might visit a node multiple time and a fresh bfs might start from there.....and this might happen for most of the v nodes. so, the time complexity of bfs code is not O(V+E) it is more than that might be O(E.V).
Why this DFS solution is going in infinite loop ?
class Solution {
boolean[] visited;
HashMap cost;
public int networkDelayTime(int[][] times, int n, int k) {
Map graph = buildGraph(times,k);
visited = new boolean[n];
cost = new HashMap();
Integer ans = 0;
dfs(graph, 0, k);
if(cost.size() != n)
{
return -1;
}
for (java.util.Map.Entry e: cost.entrySet()) {
ans = Math.max(ans, e.getValue());
}
return ans;
}
void dfs(Map graph, int curPath, int curNode )
{
if(!graph.containsKey(curNode))
{
// update HashMap
if(cost.containsKey(curNode))
{
cost.put(curNode, Math.min(cost.get(curNode), curPath));
}else{
cost.put(curNode, curPath);
}
return;
}
if(visited[curNode-1])
{
return;
}
visited[curNode-1] = true;
if(cost.containsKey(curNode))
{
cost.put(curNode, Math.min(cost.get(curNode), curPath));
}else{
cost.put(curNode, curPath);
}
for (int[] endNode : graph.get(curNode)) {
dfs(graph, curPath + endNode[1], endNode[0]);
}
visited[curNode-1] = false;
}
Map buildGraph(int[][] times, int startNode)
{
Map graph = new HashMap();
for (int[] time : times) {
int start = time[0];
int end = time[1];
int weight = time[2];
if(graph.containsKey(start))
{
graph.get(start).add(new int[]{end,weight});
}else{
List endNodeAndWeightPairList = new ArrayList();
endNodeAndWeightPairList.add(new int[]{end,weight});
graph.put(start, endNodeAndWeightPairList);
}
}
return graph;
}
void printGraph(Map graph)
{
for ( java.util.Map.Entry e : graph.entrySet()) {
System.out.print(e.getKey() + " -> ");
System.out.print("{");
for (int[] edge : e.getValue()) {
System.out.print(Arrays.toString(edge));
}
System.out.println("}");
}
}
}
Please solve this ques using topological sort technique there are cases for which it is not working . I am putting my code down here.
class Solution {
public:
int networkDelayTime(vector& times, int n, int k) {
unordered_map adj;
int signaltime [n+1][n+1];
vector indegree (n+1 , 0);
vector indegree1 (n+1 , 0);
indegree[0]=-1;
indegree1[0]=-1;
for(auto i :times)
{
vector temp = i;
int m = temp[0];
int n = temp[1];
int p = temp[2];
adj[m].push_back(n);
signaltime[m][n]=p;
indegree[n]++;
indegree1[n]++;
}
if(adj.find(k)==adj.end()) return -1;
// checking cycle in graph
int count=0;
queue qu;
for(int i=0;i
Same problem bro. If you got some solution then plz send ....
Same problem bro. If you got some solution then plz send ....