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

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 .

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

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

@@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.

@@rashmidhant3364 Yes, you might be right.

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)

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.

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.

@Gabriel Wilder fuck off and stop trying to scam people

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

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

On a regular graph, I would recommend Dijkstras algorithm. There's also Bellman ford and Floyd warshall u can look into. ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-pSqmAO-m7Lk.html

Yes, topological sort is necessary.

BFS doesn't work for weighted edges

Dfs

You arbitrarity choose one

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

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

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

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.

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.

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

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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-oDqjPvD54Ss.html

@@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.

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.

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

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

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.

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

same question

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

good eye !

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

there is no cycle, look carefully

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