Shortest/Longest path on a Directed Acyclic Graph (DAG) | Graph Theory

Solution to finding the shortest (and longest) path on a Directed Acyclic Graph (DAG) using a topological sort in combination with dynamic programming.
Topological sort video:
• Topological Sort Algor...
Github source code link:
github.com/williamfiset/algor...
===================================
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix

[@ythalorossy]

@WilliamFiset Thanks you so much for the explanation. I am watching and sharing your work. These materials are amazing.

[@JJnnaatt]

Great video, just what I was looking for. Thanks!

[@GOUSETEIN]

Love ur explanation , waiting for next set of videos on algorithms. All the best :)

[@agentstona]

what explanation ? the guy is just talking to himself .. this is not how explanations are done there is a fundamental difference between actually explaining and just reading his code .

[@vivekmit06]

This is one of best lectures on graph theory on KZbin dude. He worked for 2 years to prepare this. This guy is really good in teaching. Only thing is you need to have patience.

[@DriLLFreAK100]

Thank you very much William. This just saved my life.

[@adhishmalviya2408]

But I don't get you, how can this video save your life?

[@rashmidhant3364]

@@adhishmalviya2408 He might have some crazy loan and this video helped him crack an interview which led to repayment 🤷‍♂️ So much more you can think of.

[@adhishmalviya2408]

@@rashmidhant3364 Yes, you might be right.

[@ahsanulameensabit]

joss👍 the idea of longest path is fantastic...

[@ipsitaanirban]

How does it work for -be edges ? As for example if D to E has weight of -20 then shortest path to E should have been updated as per this algo. Here d to e is mentioned as -4 which might be the reason that edge was not considered.

[@MrMacAwsome]

For the longest path, can't we just change the shortest length function to look for the max between the two distances we are comparing?

[@vincentleclere70]

Yes, it the same as changing sign. If you code from scratch it's better to use max, if you use available code the trick is usefull.

[@sorinnorris]

Yeah I think both solutions work just fine but this is a Computing algorithm, meaning that it is likely present in code and it is much more efficient to just negate all the values than to rewrite an entire function.

[@zenanchen9395]

@Gabriel Wilder fuck off and stop trying to scam people

[@bionictortoise]

You'd also have to initialize the initial values to negative infinity first instead of positive infinity

[@RushOrbit]

@@bionictortoise Unless you're using Java in which case "Integer dist = new Integer[totalNodes]" will default to all null values.

[@mehranjalali5023]

William great explanation. How would you solve this problem for a cyclic graph?

[@WilliamFiset-videos]

On a regular graph, I would recommend Dijkstras algorithm. There's also Bellman ford and Floyd warshall u can look into. kzbin.info/www/bejne/poTUnnSFYtJqgs0

[@edenberdugo6947]

that helped me very much thank you !

[@stephwliu]

On the first graph at 0:38, is that not a cycle middle lower portion of the graph, between three nodes? (You said it was acyclic)

[@jasjotsingh9278]

Hi William, question regarding the code that you shared. On line 81 you are walking over all the node(assuming nodes are from 0 to numNodes). but in case the topological ordering is such that all the nodes from 0 to start node actually fall behind the start node in topological order, in this case wont we have wrong values for the distance for all those nodes(infinite?). eg in a grpah as: 4->0->1->2->3 where 4 is strtNode value, line 81 will go from 0->4, but topological order will be 4,0,1,2,3, so by the time we reach node 4 we will only update dist for 0 . am i missing something? please let me know. also i am confused regarding the use of topsort array in general in the code snippet.

[@SathishBatsy]

Not null check on line 84 will take care of that, distance will be calculated only when start index comes in the loop, thus only the descendants of start will be given values and taken care, others would be null (i.e infinity according to his logic)

[@user-cb1vv3db8y]

When we do Longest paths by flipping signs for edge weights, do we need to topologically sort the vertices or no? Is topological sort necessary for every instance where we have negative edges in our DAG?

[@prianshubhatia2759]

Yes, topological sort is necessary.

[@waishanqiu331]

Super!

[@osoyoki]

Hi William. I think there is a mistake when you say that all trees are DAGs by definition (in the first minute), since trees are undirected (as you note a few seconds later in the video), please correct me if I'm wrong. Thank you very much for the video series :)

[@psibarpsi]

I couldn't find any definition of trees where they talk about whether trees are supoosed to be directed or undirected by definition. So, whether a tree is a DAG or not ultimately boils down to whether it is directed or undirected, IMHO. Hope this helps.

[@aiomixrecords]

U are great

[@_gathos_8450]

I love you bro, I literally love you

[@roanicaruscheng5106]

How about showing the shortest and longest path instead of calculating weight/distance?

[@nareshnepal6879]

This gives solution only for the source taken as the first node that comes after the topological sorting is done.... how can this be extended so that any node can be source??

[@ythalorossy]

Could you create a video explaining the problem and the solution for "how can this be extended so that any node can be source??" ?

[@noname-it2up]

Just change the distance to your starting node to 0 in the dist array and make the rest null or infinity and then only nodes reachable from your start node will be updated when iterating over the topological sorting of nodes

[@manikantabandla3923]

You can directly go to the source node(preferred) in the topological order and start the same algo from the source node in the topological order. And the shortest paths to the nodes that are lying to the left of source node is "infinity" (Because there exists no path).

[@enricocaprioglio3892]

it might also happen that there is no path to some elements on the right of the source node in the topological order. For instance, take the example from the video, use as source node node B and remove the edge from B to C. The topological order would still be correct but now there is no path from B to C. This might break the code I think if no other changes are made than those suggested above.

[@grn7797]

can we use BFS as well to update the mins for each node in the shortest path problem?

[@khalilshaik6161]

BFS doesn't work for weighted edges

[@ceciivanov6152]

how to modify this so i can find the longest from all paths in the graph and not the one with source A to all others? any help?

[@emelcakir945]

Dfs

[@UdayTejaOriginal]

Hi William, what would happen in the case when there are two nodes with indegree 0?

[@tylerferron7660]

You arbitrarity choose one

[@niksgupta36]

what is NP-Hard??

[@anuruddhapremalal]

Great explanation!. How do we obtain a list of nodes for the shortest paths?

[@WilliamFiset-videos]

Anuruddha Premalal You'll need additional memory to do that. Allocate an array called "previous" of size n with all null values. Every time u can relax an edge, update the parent of node i in the previous array. Then work backwards from the end node rebuilding the path. Does that make sense? See the BFS example in my Algorithms repo. Specifically the 'reconstructPath' method: github.com/williamfiset/Algorithms/blob/master/com/williamfiset/algorithms/graphtheory/BreadthFirstSearchAdjacencyListIterative.java

[@marjavanderwind4251]

@WilliamFiset I can see that we have found the length (!) of the shorthest path, but how to deduct the shorthest path itself? Can you hint how to incorporate this in the code?

[@WilliamFiset-videos]

I believe you should be able to capture the path of nodes which make up the path with some extra information. Check out the path reconstruction method in my BFS video, it should be very similar concept: kzbin.info/www/bejne/pXXUm4OseZpnidU

[@agentstona]

@@WilliamFiset-videos replying vaguely cryptically doesn't actually answer her question . with the amount of characters you typed just to give a vague reply you could have just given her the direct pseudo steps . that's would have been more helpful to remain on point.

[@Aditya-pl3xg]

make a parent array and in the loop for(auto u : adj[v]) - parent[u] = v. this way you can retrace path by following pointers. This is a general technique for tracing paths.

[@Am-ug9np]

But how do you backtrack to actually find the path? Following along with this, all I could manage was finding the length of the path. I don't see how knowing the shortest path to every node actually helps you backtrack.

[@priyadarshansingh8021]

Keep a parent array and update the parent node at each relaxing step.

[@konstantinrebrov675]

What does NP-Hard mean?

[@kroypatcha]

If you can not find answer in O(n^k) k is a constant such as 0,1,2... and also you can’t verify if answer is correct in O(n^k) -> NP-hard

[@studytime4048]

Instead of finding the topological sort, can't we just process the nodes in breadth first search manner?

[@durgeshvalecha5718]

same question

[@Shreyas535]

This is a weighted graph. How will BFS give the shortest path?

[@harishvemula6709]

I have a doubt , does this algorithm works for negative edges

[@RR8401674]

As mentioned in the video, this linear O(V+E) solution works for DAG (where you can topologically sort the vertices, in other words no cycles). For more general case with cycles your best bet is Bellman-Ford (with much worse runtime: O(VE))

[@johnnywilson3071]

How would this work for C++ where you want to avoid use of NULL.

[@anonymoussloth6687]

For the SSSP algo, you are assuming that the source node is the node that is first when we topological sort the DAG. What if the source node was say D at 3:40?

[@kaze3311]

To find shortest distance from D using this Kahn's algorithm, I think after getting the top sorted array, we can start from the 1st node and start removing all their outgoing edges, till we reach node D. After this "preprocessing", D will be the single source on the new graph and Kahn's algorithm can be used to find shorted path from D. However, it's also possible that after the "preprocessing" there may be other 0-incoming-edge nodes other than D, i.e., the new graph has multiple sources, such as X and Y. In this case, Kahn's algorithm cannot be used to find the shortest path, as the shortest dist to a non-source node may be from Y while the intended source is X, and we cannot tell whether it's from X or from Y.

[@GOODBOY-vt1cf]

1:00

[@GOODBOY-vt1cf]

1:21

[@MayankKumar-mn3dg]

I tried Doing the longest path problem with Dijkstra on a DAG with negative edges. But it keeps getting TLEd (even with priority queue) .... what is the reason behind this ??

[@tweakter]

Much surprised and happy that you use java over cpp 😍

[@leonardosuriano8260]

0:32 there is a cycle in the graph!! It is not a DAG!

[@mardy_magnus]

good eye !

[@leonardosuriano8260]

@Gaston Fontenla now there is not, it was corrected! ;)

[@kaushalyadav7537]

there is no cycle, look carefully

[@leonardosuriano8260]

@@kaushalyadav7537 now not. it was corrected, as I already said!

[@anfield6321]

Dont mesmerize people into graph theory with your voice.

[@truekili9215]

Why would you title the second chapter Dijkstra algortithm if it's not dijkstra's algorithm and it's just DAG relaxation. It's extremely misleading and annoying to have to go watch your other videos in order to know that you're not even talking about the algorithm you titled the chapter after.

[@zxoowoo6094]

For longest path, it cannot work😢 we DELETE A C G H one by one.... cannot get the chance to find H Through B