Network Delay Time | Leetcode #743

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:

=======================================================================

USEFUL LINK:-

[大盗江南]

amazing buddy, i was wondering should we use a set to keep track of visited nodes... but your idea is better!

[theghostwhowalk]

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.

[ratneshpal]

Sir, I am eagerly waiting for DP course

[kc]

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

[tomsabu]

Does this version of bfs replace dijkstra related problems?

[paneerlovr]

Are you writing this all with a mouse on a computer? Great video, how did you make this, are you using a stylus?

[yihongliu]

I am having trouble understanding why the time complexity of this problem is different from the one of Dijkstra?

[amiriqbal]

This may not work when the graph has a cycle in it!

[shashanksinha]

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 should be the maximum of minimum time to reach each node, in that case signal would be reaching all nodes

[HimanshuYadav-btzk]

you didn't dealt with cycle case ? I think this is incomplete solution

[ashutoshkumar]

Why use dijktsra then since we can find shortest path using bfs?

[raghugore]

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,
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

[chayanbharbittu]

Do I need to learn semester subjects like digital logic, discrete structure engineering math etc for interview purpose? please help sir🙏

[aradhyakapoor]

@Tech Dose, isn't the time complexity O(V*E)?

[divyakumari]

Can u please make a video on word wrap problem sir??

[gouravgoel]

sir, i am from jadavpur university, and I want to know wether you also studied at jadavpur university?

[vaibhavanuragi]

Why haven't we used this method in the Dijkstra algorithm to reduce its time complexity from O(ElogV) to O(V+E)?

[danny]

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)?

[gaurika]

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.

[aniketbhura]

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 times, int n, int k) {
unordered_map <int, vector <int>> adj;
int signaltime [n+1][n+1];
vector <int> indegree (n+1, 0);
vector <int> indegree1 (n+1, 0);
indegree[0]=-1;
indegree1[0]=-1;
for(auto i :times)
{
vector <int> 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 <int> qu;
for(int i=0;i<n+1;i++)
{
if(indegree[i]==0)
{
qu.push(i);
}
}

while(qu.empty()==false)
{
int c = qu.front();
qu.pop();
count++;

vector <int> temp3 = adj[c];
for(int i=0;i<temp3.size();i++)
{
indegree[temp3[i]]--;
if(indegree[temp3[i]]==0)
qu.push(temp3[i]);
}
}

if(count!=n) return -1;

// cycle check complete

// find any topological sorted order of nodes

vector <int> topsort;
queue <int> qu1;

for(int i=0;i<n+1;i++)
{
if(indegree1[i]==0)
qu1.push(i);
}
while(qu1.empty()==false)
{
int c = qu1.front();
qu1.pop();
topsort.push_back(c);
vector <int> temp4 = adj[c];

for(int i=0;i<temp4.size();i++)
{
indegree1[temp4[i]]--;
if(indegree1[temp4[i]]==0)
{ qu1.push(temp4[i]); }

}
}


// now we have topological sorted sequence in topsort.
// now finding shortest path for each of the node and storing it in ans.

vector <int> ans(n+1, INT_MAX);
ans[0]=-1;
ans[k]=0;

for(int i=0;i<topsort.size();i++)
{
vector <int> temp5 = adj[topsort[i]];
int n = ans[topsort[i]];

for(int j=0;j<temp5.size();j++)

{
int m = ans[temp5[j]];
int timesig =

if( m > timesig + n )
{

ans[temp5[j]] = ans[topsort[i]] + ;

}

}
}
// returning max value in ans vector, directly sating from i=1 since , ans[0] = -1 which was done .
int finalans=0;
for(int i=1;i<ans.size();i++)
{
finalans= max(finalans, ans[i]) ;
}
return finalans;

}
};