Longest path in a Directed Acyclic graph | Dynamic Programming | GeeksforGeeks

[@babbarutkarsh7770]

This time gfg did a good thing by assigning you to teach us.

[@qR7pK9sJ2t]

Making us understand the problem - A
Getting us to understand the approach - A
Presentation - A
Writing in Code - F

[@priyankarrajgupta4198]

Good explanation.
NIT: Actually we can skip visited array using DP at its place.

[@ericacm]

Great explanation

[@shubhambansal1145]

Wrong time complexity. It should be O(V+E) as we are doing DFS and travelling all edges of the graph.

[@yashbansal1520]

yes

[@Gabriel-wq4ln]

Could someone explain me why?

[@peacan_in_a_can]

This video really helped me a lot! I appreciate it!

[@SHASHANKRUSTAGII]

Wow. I LOVED this video. It might come in GATE 2021

[@camilabbertelli]

hey! is there a way to do this in an iterative form?

[@casper-thenaughtybeagle8534]

this was so simple, yet beautiful

[@jaatharsh]

Bang on Target, we are loving this.
As always thanks for posting such excellent quality content, keep them rolling.

[@richdavis9690]

Any way you could add some test cases for the write up on the site? There isn't a problem anywhere that has them.

[@smhhoseinee]

I enjoyed it . thank u

[@will0rosenbergova]

the hot dude without Indian accent was actually a nice surprise :D

[@easy_3d]

Can you make a video on all possible paths from source to destination using dynamic programming?

[@Vikassharma-rq5bh]

cin>>n>>m;
for(int i=1;iq;
while(m--){
int a,b,c;
cin>>a>>b>>c;
if(a==b){
dis[a][b]=0;
dis[b][a]=0;
}
dis[a][a]=0;
dis[b][b]=0;
dis[a][b]=min(dis[a][b],c);
dis[b][a]=min(dis[a][b],c);
}
for(int k=1;k>b;
if(dis[a][b]

[@himanshubhatt8565]

Great explanation ☺

[@Parth.Deshpande]

nice explanation !!!!!

[@AlexanderOnTube]

Excellent explanation! Great job!

[@hopechan697]

really useful

[@shanmugamudhaya7726]

Why the need for visited?

[@bubblesgrappling736]

how would this work if we were looking for a path from s to t? , that being where we already specified where we want to start and end

[@adilbhatti6299]

dfs?

[@shivkj1697]

What is the definition of longest path in DAG?
Can you traverse same node multiple time while making sure chosen edge is not repeated?

[@ianwulf24]

Man. This kind of helps my issue, but I'm really trying to determine the longest path between two nodes in a weighted, directed graph. Not just the longest path in the graph in general. Hmmmmmmmmm.

[@dhtmaxxer]

bros a lefty... dam-

[@Saksham_1718]

He is so gay - Arpit bala

[@Dennis-Hu]

Great explanation