title

G-27. Shortest Path in Directed Acyclic Graph - Topological Sort

description

GfG-Problem Link: https://bit.ly/3dJdQXE
C++/Java/Codes and Notes Link: https://takeuforward.org/data-structure/shortest-path-in-directed-acyclic-graph-topological-sort-g-27/
DP Series: https://www.youtube.com/watch?v=FfXoiwwnxFw&list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY
SDE Sheet: https://takeuforward.org/interviews/strivers-sde-sheet-top-coding-interview-problems/
Check out our Website for curated resources: https://www.takeuforward.org/
Our Second Channel: https://www.youtube.com/channel/UCvEKHATlVq84hm1jduTYm8g
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: https://practice.geeksforgeeks.org/courses
Code "takeuforward" for 20% off on sys-design: https://get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: https://wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: https://indmoney.onelink.me/RmHC/idjex744
Earn 100 rs by making a Grow Account for investing: https://app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: https://linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------

detail

{'title': 'G-27. Shortest Path in Directed Acyclic Graph - Topological Sort', 'heatmap': [{'end': 559.144, 'start': 511.24, 'weight': 0.815}, {'end': 1006.594, 'start': 971.924, 'weight': 0.704}, {'end': 1213.854, 'start': 1191.443, 'weight': 0.719}, {'end': 1293.718, 'start': 1228.4, 'weight': 0.948}], 'summary': "Covers topics such as finding the shortest path in a directed acyclic graph using topological sort and edge relaxation, topological sorting methods using dfs or bfs, dijkstra's algorithm for relaxing edges, and the implementation of graph algorithms in c++ and java with an emphasis on time and space complexity.", 'chapters': [{'end': 230.368, 'segs': [{'end': 32.594, 'src': 'embed', 'start': 3.151, 'weight': 1, 'content': [{'end': 4.412, 'text': 'Hey everyone, welcome back to the channel.', 'start': 3.151, 'duration': 1.261}, {'end': 5.973, 'text': 'I hope you guys are doing extremely well.', 'start': 4.432, 'duration': 1.541}, {'end': 11.057, 'text': 'So today we will be solving the problem shortest path in directed acyclic graph.', 'start': 6.373, 'duration': 4.684}, {'end': 15.1, 'text': 'Given a directed acyclic graph, find the shortest path from the source.', 'start': 11.497, 'duration': 3.603}, {'end': 20.364, 'text': "I've clearly stated that the source will always be 0 to all the vertex.", 'start': 15.521, 'duration': 4.843}, {'end': 25.528, 'text': 'Okay, so basically what does the problem state? Yeah, given a DAG.', 'start': 20.825, 'duration': 4.703}, {'end': 32.594, 'text': "Now what is a DAG? If you remember, it's a directed graph with no cycles.", 'start': 25.969, 'duration': 6.625}], 'summary': 'Solving shortest path in a directed acyclic graph with source always at 0.', 'duration': 29.443, 'max_score': 3.151, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U3151.jpg'}, {'end': 159.195, 'src': 'embed', 'start': 132.617, 'weight': 0, 'content': [{'end': 138.059, 'text': "okay, i'll be, uh, combining topo sort with some relaxation of edges to solve this.", 'start': 132.617, 'duration': 5.442}, {'end': 148.681, 'text': "so i'll write the steps, and the process that i'll follow is first i'll tell you the algorithm, then we'll go and code it so that after this process,", 'start': 138.059, 'duration': 10.622}, {'end': 152.189, 'text': 'you have a very strong hold of what we are doing.', 'start': 149.707, 'duration': 2.482}, {'end': 155.752, 'text': 'Once you understand this, I will tell you the intuition.', 'start': 152.669, 'duration': 3.083}, {'end': 159.195, 'text': 'Okay, You might think why not intuition at the start?', 'start': 156.372, 'duration': 2.823}], 'summary': 'Combining topo sort with edge relaxation to solve problem, followed by algorithm explanation, coding process, and intuition.', 'duration': 26.578, 'max_score': 132.617, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U132617.jpg'}, {'end': 236.113, 'src': 'embed', 'start': 208.053, 'weight': 2, 'content': [{'end': 210.715, 'text': 'this time it will be list of pairs either.', 'start': 208.053, 'duration': 2.662}, {'end': 215.599, 'text': 'you are in c plus plus, it will be vector of pairs what you will store.', 'start': 210.715, 'duration': 4.884}, {'end': 221.603, 'text': 'if you are doing a java, it will be array list of pairs that you will store in this particular thing.', 'start': 215.599, 'duration': 6.004}, {'end': 227.205, 'text': 'remember the third lecture, where i told you how to store graphs if they have edge weights.', 'start': 222.301, 'duration': 4.904}, {'end': 230.368, 'text': 'you always declare it as pairs and you store pairs.', 'start': 227.205, 'duration': 3.163}, {'end': 236.113, 'text': 'where the first guy will be the adjacent node, the second guy will be the weight of that edge.', 'start': 230.368, 'duration': 5.745}], 'summary': 'Store graph edge weights as pairs in c++ (vector) or java (array list).', 'duration': 28.06, 'max_score': 208.053, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U208053.jpg'}], 'start': 3.151, 'title': 'Shortest path in directed acyclic graph', 'summary': 'Discusses finding the shortest path in a directed acyclic graph from the source (0) to all other nodes using topological sort and edge relaxation, determining the shortest distance for each node based on given edge weights.', 'chapters': [{'end': 230.368, 'start': 3.151, 'title': 'Shortest path in directed acyclic graph', 'summary': 'Discusses finding the shortest path in a directed acyclic graph from the source (0) to all other nodes, using a combination of topological sort and edge relaxation, where the shortest distance for each node is determined based on given edge weights.', 'duration': 227.217, 'highlights': ['The problem statement is to find the shortest path from the source (0) to all other nodes in a directed acyclic graph (DAG), with the source always being 0. This sets the context for the problem and outlines the specific objective of determining the shortest paths.', 'The approach combines topological sort with edge relaxation to solve the problem, marking a slight variation from the traditional topological sort algorithm. This highlights the unique approach taken to solve the problem and introduces the concept of edge relaxation.', 'The graph representation uses pairs to store the adjacency list, with each pair indicating the neighboring node and the corresponding edge weight. This explains the use of pairs to represent the adjacency list, providing insight into the data structure used for graph representation.']}], 'duration': 227.217, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U3151.jpg', 'highlights': ['The approach combines topological sort with edge relaxation to solve the problem, marking a slight variation from the traditional topological sort algorithm.', 'The problem statement is to find the shortest path from the source (0) to all other nodes in a directed acyclic graph (DAG), with the source always being 0. This sets the context for the problem and outlines the specific objective of determining the shortest paths.', 'The graph representation uses pairs to store the adjacency list, with each pair indicating the neighboring node and the corresponding edge weight. This explains the use of pairs to represent the adjacency list, providing insight into the data structure used for graph representation.']}, {'end': 505.178, 'segs': [{'end': 347.139, 'src': 'embed', 'start': 252.976, 'weight': 0, 'content': [{'end': 260.88, 'text': "For this graph, assume the source to be six because I don't want you to be sticking with zero because that will not help you out.", 'start': 252.976, 'duration': 7.904}, {'end': 265.864, 'text': 'So we can have any source because the interviewer might give you the question as stating as any source.', 'start': 260.921, 'duration': 4.943}, {'end': 266.825, 'text': 'So any source.', 'start': 266.224, 'duration': 0.601}, {'end': 268.166, 'text': 'Okay, So what is the step one?', 'start': 266.865, 'duration': 1.301}, {'end': 274.55, 'text': 'so the step one of the algorithm is very simple do a toposort, do a toposort on the graph.', 'start': 268.866, 'duration': 5.684}, {'end': 278.192, 'text': 'ps. do a toposort on the graph.', 'start': 274.55, 'duration': 3.642}, {'end': 280.793, 'text': 'now, how many ways do you know to do a toposort?', 'start': 278.192, 'duration': 2.601}, {'end': 281.894, 'text': 'there are two ways.', 'start': 280.793, 'duration': 1.101}, {'end': 283.215, 'text': 'one is the dfs way.', 'start': 281.894, 'duration': 1.321}, {'end': 284.376, 'text': 'one is the bfs way.', 'start': 283.215, 'duration': 1.161}, {'end': 285.877, 'text': 'do whichever you wish to.', 'start': 284.376, 'duration': 1.501}, {'end': 291.88, 'text': 'i just want the toposort for this particular dag, which is the directed acyclic graph.', 'start': 285.877, 'duration': 6.003}, {'end': 295.725, 'text': "so let's quickly do the toposort for this dag.", 'start': 291.88, 'duration': 3.845}, {'end': 298.309, 'text': "so i'll be using the dfs method to find the toposort.", 'start': 295.725, 'duration': 2.584}, {'end': 300.512, 'text': 'so you know, the dfs method is very simple.', 'start': 298.309, 'duration': 2.203}, {'end': 304.477, 'text': 'we always take a stack data structure which stores the toposort.', 'start': 300.512, 'duration': 3.965}, {'end': 308.362, 'text': 'whenever we complete the dfs for a given node, we put it into the stack.', 'start': 304.477, 'duration': 3.885}, {'end': 310.063, 'text': 'take a visited node.', 'start': 308.923, 'duration': 1.14}, {'end': 311.124, 'text': 'that is what we take.', 'start': 310.063, 'duration': 1.061}, {'end': 322.968, 'text': 'and we always run something like this for i equal to 0, and we go on till 6 and we say if not visited of i, then please call the dfs for i.', 'start': 311.124, 'duration': 11.844}, {'end': 326.109, 'text': 'if you remember, this is always done for the components, right.', 'start': 322.968, 'duration': 3.141}, {'end': 328.87, 'text': "so what's the first value of i?", 'start': 326.109, 'duration': 2.761}, {'end': 329.45, 'text': "that's zero.", 'start': 328.87, 'duration': 0.58}, {'end': 332.132, 'text': "so we'll go and call the dfs for zero.", 'start': 329.45, 'duration': 2.682}, {'end': 333.973, 'text': 'the dfs of zero is called.', 'start': 332.132, 'duration': 1.841}, {'end': 338.675, 'text': 'whenever the dfs of zero is called, please make sure it is marked as visited.', 'start': 333.973, 'duration': 4.702}, {'end': 341.276, 'text': 'now who are zeros adjacent nodes?', 'start': 338.675, 'duration': 2.601}, {'end': 344.177, 'text': 'it appears that zeros adjacent node is one.', 'start': 341.276, 'duration': 2.901}, {'end': 347.139, 'text': 'so go and call the dfs for one perfect.', 'start': 344.177, 'duration': 2.962}], 'summary': 'Algorithm involves performing a toposort on a directed acyclic graph using dfs or bfs methods, with six as the assumed source.', 'duration': 94.163, 'max_score': 252.976, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U252976.jpg'}, {'end': 505.178, 'src': 'embed', 'start': 461.565, 'weight': 5, 'content': [{'end': 463.325, 'text': 'so no further dfs calls.', 'start': 461.565, 'duration': 1.76}, {'end': 465.405, 'text': 'put it into the stack and go back.', 'start': 463.325, 'duration': 2.08}, {'end': 474.827, 'text': 'so apparently, once this for loop has been completed, all the dfs calls have been completed, this stack will store the topo sort.', 'start': 465.405, 'duration': 9.422}, {'end': 477.728, 'text': "now, if i quickly erase this off, let's quickly erase this off.", 'start': 474.827, 'duration': 2.901}, {'end': 482.351, 'text': 'the step one i can say has been completed and the topo sort is very simple.', 'start': 478.428, 'duration': 3.923}, {'end': 489.255, 'text': 'it is six, five, four, two, zero, one, three, and if you carefully see, there is an edge between zero to one.', 'start': 482.351, 'duration': 6.904}, {'end': 491.216, 'text': 'so zero appears before one.', 'start': 489.255, 'duration': 1.961}, {'end': 493.297, 'text': 'there is an edge between two to three.', 'start': 491.216, 'duration': 2.081}, {'end': 495.379, 'text': 'the two appears before three.', 'start': 493.297, 'duration': 2.082}, {'end': 497.96, 'text': 'so this is indeed a valid topo sort.', 'start': 495.379, 'duration': 2.581}, {'end': 501.983, 'text': 'i can easily say that now what is step two, step two, is very, very simple.', 'start': 497.96, 'duration': 4.023}, {'end': 505.178, 'text': 'You take out all the nodes from the stack 1x1..', 'start': 502.697, 'duration': 2.481}], 'summary': 'Dfs algorithm completed, yielding valid topological sort: 6, 5, 4, 2, 0, 1, 3.', 'duration': 43.613, 'max_score': 461.565, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U461565.jpg'}], 'start': 230.368, 'title': 'Topological sorting of directed acyclic graphs', 'summary': 'Discusses the process of finding the topological sort of a directed acyclic graph (dag) with emphasis on flexibility in choosing the source, using dfs or bfs methods. it explains the dfs method for toposort, utilizing a stack data structure and calling dfs for each unvisited node. additionally, it explains the process of performing a depth first search (dfs) algorithm to create a topological sort of the given graph.', 'chapters': [{'end': 298.309, 'start': 230.368, 'title': 'Dag topological sort algorithm', 'summary': 'Discusses the process of finding the topological sort of a directed acyclic graph (dag), emphasizing the flexibility in choosing the source and the requirement of performing a toposort using either the depth-first search (dfs) or breadth-first search (bfs) method.', 'duration': 67.941, 'highlights': ["The interviewer may ask the question with any given source, requiring flexibility in choosing the source. The source for the algorithm is not fixed at zero, allowing flexibility to choose any given source, as per the interviewer's question.", "The step one of the algorithm involves performing a toposort on the graph using either the DFS or BFS method. The algorithm's initial step is to conduct a toposort on the graph, offering the flexibility to use either the DFS or BFS method to achieve this.", 'The toposort can be executed using either the DFS or BFS method. The toposort process can be accomplished through two methods: the depth-first search (DFS) or breadth-first search (BFS), providing the candidate with a choice.']}, {'end': 391.233, 'start': 298.309, 'title': 'Dfs method for toposort', 'summary': 'Explains the dfs method for toposort, using a stack data structure to store the toposort and calling dfs for each unvisited node, resulting in a toposorted stack.', 'duration': 92.924, 'highlights': ['The DFS method uses a stack data structure to store the toposort, putting each node into the stack after completing its DFS (Depth First Search) traversal.', 'The process involves calling DFS for each unvisited node, such as in the given example, where DFS is called for nodes 0, 1, and 3.', 'Marking nodes as visited and identifying their adjacent nodes is crucial in the DFS process, as demonstrated in the explanation of calling DFS for node 0 and its adjacent nodes.', 'The completion of DFS for a node results in adding it to the toposorted stack, as illustrated in the explanation of completing DFS for node 3 and adding it to the stack.']}, {'end': 505.178, 'start': 391.233, 'title': 'Dfs algorithm and topological sorting', 'summary': 'Explains the process of performing a depth first search (dfs) algorithm to create a topological sort of the given graph, resulting in a valid topological order of nodes.', 'duration': 113.945, 'highlights': ['The stack will store the topo sort once all the dfs calls have been completed. The stack stores the topological sort of the graph, resulting in a valid topological order of nodes.', 'The valid topological sort is 6, 5, 4, 2, 0, 1, 3, based on the completed DFS calls. The valid topological sort of the graph is 6, 5, 4, 2, 0, 1, 3, determined by the completed DFS calls.', 'Nodes are taken out from the stack one by one for the next step in the process. The next step involves removing nodes from the stack one by one to complete the topological sorting process.']}], 'duration': 274.81, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U230368.jpg', 'highlights': ['The toposort can be executed using either the DFS or BFS method.', 'The step one of the algorithm involves performing a toposort on the graph using either the DFS or BFS method.', 'The interviewer may ask the question with any given source, requiring flexibility in choosing the source.', 'The process involves calling DFS for each unvisited node, such as in the given example, where DFS is called for nodes 0, 1, and 3.', 'The DFS method uses a stack data structure to store the toposort, putting each node into the stack after completing its DFS (Depth First Search) traversal.', 'The stack will store the topo sort once all the dfs calls have been completed.', 'The valid topological sort is 6, 5, 4, 2, 0, 1, 3, based on the completed DFS calls.']}, {'end': 952.187, 'segs': [{'end': 560.744, 'src': 'heatmap', 'start': 505.798, 'weight': 0, 'content': [{'end': 507.919, 'text': 'Take the nodes out of the stack 1x1.', 'start': 505.798, 'duration': 2.121}, {'end': 510.06, 'text': 'Nodes out of stack.', 'start': 508.399, 'duration': 1.661}, {'end': 512.38, 'text': 'And relax the edges.', 'start': 511.24, 'duration': 1.14}, {'end': 515.081, 'text': "You'll hear this term a lot going forward.", 'start': 512.76, 'duration': 2.321}, {'end': 516.302, 'text': 'And relax the edges.', 'start': 515.241, 'duration': 1.061}, {'end': 519.863, 'text': 'Okay This is the step 2.', 'start': 517.342, 'duration': 2.521}, {'end': 523.004, 'text': 'So, in order to relax the edges, we need to declare a distance array.', 'start': 519.863, 'duration': 3.141}, {'end': 525.025, 'text': 'And that should be marked with infinity.', 'start': 523.563, 'duration': 1.462}, {'end': 525.625, 'text': "Let's do it.", 'start': 525.185, 'duration': 0.44}, {'end': 532.954, 'text': "the distance error has been declared and what you'll do initially is just make sure everything is marked as infinity.", 'start': 526.772, 'duration': 6.182}, {'end': 535.495, 'text': "now let's start relaxation of the edges.", 'start': 532.954, 'duration': 2.541}, {'end': 541.717, 'text': 'but before that, please make sure, whatever is your source node, just go to that source node and make it zero.', 'start': 535.495, 'duration': 6.222}, {'end': 547.899, 'text': 'just make sure that you go to that source node and say that hey, i know one thing if you start from six and if you end at six,', 'start': 541.717, 'duration': 6.182}, {'end': 550.14, 'text': 'the distance that you will take will always be zero.', 'start': 547.899, 'duration': 2.241}, {'end': 551.841, 'text': 'so make sure you do that okay.', 'start': 550.14, 'duration': 1.701}, {'end': 556.122, 'text': 'next, whatever is on the stack stop, this is stack stop.', 'start': 551.841, 'duration': 4.281}, {'end': 559.144, 'text': 'stack is always last in first stop.', 'start': 556.122, 'duration': 3.022}, {'end': 560.744, 'text': 'so the last n was six.', 'start': 559.144, 'duration': 1.6}], 'summary': 'Relax edges by declaring infinity distance array and starting from source node with 0 distance.', 'duration': 54.946, 'max_score': 505.798, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U505798.jpg'}, {'end': 710.739, 'src': 'embed', 'start': 681.74, 'weight': 5, 'content': [{'end': 683.621, 'text': "it's clearly states as three.", 'start': 681.74, 'duration': 1.881}, {'end': 684.862, 'text': 'the distance is three.', 'start': 683.621, 'duration': 1.241}, {'end': 686.083, 'text': 'what does it mean?', 'start': 684.862, 'duration': 1.221}, {'end': 686.884, 'text': 'what was whatever?', 'start': 686.083, 'duration': 0.801}, {'end': 687.744, 'text': 'was the source node?', 'start': 686.884, 'duration': 0.86}, {'end': 691.027, 'text': 'in order to get to node five, i required a distance of three.', 'start': 687.744, 'duration': 3.283}, {'end': 692.368, 'text': 'that is the meaning of it.', 'start': 691.027, 'duration': 1.341}, {'end': 695.571, 'text': 'so for node five, look at the uh nodes.', 'start': 692.368, 'duration': 3.203}, {'end': 697.812, 'text': 'so the nearby node is four.', 'start': 695.571, 'duration': 2.241}, {'end': 699.574, 'text': 'so the nearby node is four.', 'start': 697.812, 'duration': 1.762}, {'end': 702.856, 'text': 'how much will it take if it goes from four, five to four?', 'start': 699.574, 'duration': 3.282}, {'end': 705.778, 'text': 'one plus one is what it will take.', 'start': 702.856, 'duration': 2.922}, {'end': 707.778, 'text': "let's uh, let's take the distance.", 'start': 705.778, 'duration': 2}, {'end': 710.739, 'text': 'the previous date took three in order to reach from six to five.', 'start': 707.778, 'duration': 2.961}], 'summary': 'Nodes have specific distances, e.g., 3, between them, with specific routes and distances mentioned.', 'duration': 28.999, 'max_score': 681.74, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U681740.jpg'}, {'end': 952.187, 'src': 'embed', 'start': 910.517, 'weight': 3, 'content': [{'end': 919.119, 'text': 'so once you have done the step 2, you can see that the distance array actually stores all the shortest distance from the source.', 'start': 910.517, 'duration': 8.602}, {'end': 923.9, 'text': '6 and the toposort is empty, and we have figured out our.', 'start': 919.119, 'duration': 4.781}, {'end': 926.48, 'text': 'this is our answer.', 'start': 923.9, 'duration': 2.58}, {'end': 928.401, 'text': 'yes, this is what our answer is.', 'start': 926.48, 'duration': 1.921}, {'end': 931.501, 'text': "so i hope you've understood the algorithm.", 'start': 928.401, 'duration': 3.1}, {'end': 933.722, 'text': "it's very straightforward and simple.", 'start': 931.501, 'duration': 2.221}, {'end': 935.462, 'text': 'figure out the toposot.', 'start': 933.722, 'duration': 1.74}, {'end': 940.864, 'text': "once you've done that, take one one, node out and just keep on updating the distance array.", 'start': 935.462, 'duration': 5.402}, {'end': 944.385, 'text': "keep on updating the distance array every time once you're done with this.", 'start': 940.864, 'duration': 3.521}, {'end': 946.385, 'text': 'this is your particular answer.', 'start': 944.385, 'duration': 2}, {'end': 947.425, 'text': "what's the intuition?", 'start': 946.385, 'duration': 1.04}, {'end': 947.866, 'text': 'after the code?', 'start': 947.425, 'duration': 0.441}, {'end': 949.066, 'text': "i'll tell you.", 'start': 947.866, 'duration': 1.2}, {'end': 951.126, 'text': "so i hope you've understood the entire algorithm.", 'start': 949.066, 'duration': 2.06}, {'end': 952.187, 'text': "now it's time to code it up.", 'start': 951.126, 'duration': 1.061}], 'summary': 'The algorithm calculates shortest distances from the source for a specific task.', 'duration': 41.67, 'max_score': 910.517, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U910517.jpg'}], 'start': 505.798, 'title': "Dijkstra's algorithm and shortest path", 'summary': "Explains relaxing edges in dijkstra's algorithm and demonstrates the shortest path algorithm, providing detailed step-by-step explanations and examples of updating the distance array for each node.", 'chapters': [{'end': 572.129, 'start': 505.798, 'title': "Relaxing edges in dijkstra's algorithm", 'summary': "Explains the process of relaxing edges in dijkstra's algorithm, including initializing the distance array and marking it with infinity, setting the source node's distance to zero, and removing nodes from the stack while updating their distances.", 'duration': 66.331, 'highlights': ["The process involves declaring a distance array and marking it with infinity, then setting the source node's distance to zero, and subsequently removing nodes from the stack while updating their distances.", 'It is important to initialize the distance array with infinity and then set the distance of the source node to zero before proceeding with the relaxation of edges.', 'The key step in relaxing the edges involves updating the distances of the nodes while taking them out of the stack, ensuring the correct distances are maintained for optimal pathfinding.']}, {'end': 952.187, 'start': 572.129, 'title': 'Shortest path algorithm', 'summary': "Discusses the shortest path algorithm, demonstrating the process of finding the shortest distance from a source node to all other nodes in a graph using dijkstra's algorithm, with detailed step-by-step explanations and examples of updating the distance array for each node.", 'duration': 380.058, 'highlights': ["The chapter discusses the process of finding the shortest distance from a source node to all other nodes in a graph using Dijkstra's algorithm. Demonstrates the application of Dijkstra's algorithm to find the shortest path in a graph.", 'Detailed step-by-step explanations and examples of updating the distance array for each node are provided. Provides detailed explanations and examples of the step-by-step process of updating the distance array for each node in the graph.', 'The algorithm involves identifying adjacent nodes and calculating the distance required to reach each node from the source. Explains the process of identifying adjacent nodes and calculating the distance required to reach each node from the source node.']}], 'duration': 446.389, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U505798.jpg', 'highlights': ["The process involves declaring a distance array and marking it with infinity, then setting the source node's distance to zero, and subsequently removing nodes from the stack while updating their distances.", 'It is important to initialize the distance array with infinity and then set the distance of the source node to zero before proceeding with the relaxation of edges.', 'The key step in relaxing the edges involves updating the distances of the nodes while taking them out of the stack, ensuring the correct distances are maintained for optimal pathfinding.', "The chapter discusses the process of finding the shortest distance from a source node to all other nodes in a graph using Dijkstra's algorithm. Demonstrates the application of Dijkstra's algorithm to find the shortest path in a graph.", 'Detailed step-by-step explanations and examples of updating the distance array for each node are provided. Provides detailed explanations and examples of the step-by-step process of updating the distance array for each node in the graph.', 'The algorithm involves identifying adjacent nodes and calculating the distance required to reach each node from the source. Explains the process of identifying adjacent nodes and calculating the distance required to reach each node from the source node.']}, {'end': 1299.46, 'segs': [{'end': 999.427, 'src': 'embed', 'start': 971.924, 'weight': 0, 'content': [{'end': 975.366, 'text': "so let's quickly create the graph, which will be something like vector of pair.", 'start': 971.924, 'duration': 3.442}, {'end': 976.627, 'text': 'we need to store pairs this time.', 'start': 975.366, 'duration': 1.261}, {'end': 978.909, 'text': 'so adjacency of n okay.', 'start': 976.627, 'duration': 2.282}, {'end': 982.371, 'text': 'next we go across and say ind i equal to zero, i less than n.', 'start': 978.909, 'duration': 3.462}, {'end': 985.154, 'text': 'i plus plus is something which you will do now.', 'start': 982.371, 'duration': 2.783}, {'end': 991.68, 'text': "is the next thing that i'll do is the adjacency of u, by the way, just to make your understanding better, edges of i.", 'start': 985.154, 'duration': 6.526}, {'end': 997.345, 'text': '0, because every index has a vector and the vector resembles three guys.', 'start': 991.68, 'duration': 5.665}, {'end': 999.427, 'text': 'that is the meaning of this.', 'start': 997.345, 'duration': 2.082}], 'summary': 'Creating a graph using vectors of pairs to store adjacency of n, with a vector for each index resembling three elements.', 'duration': 27.503, 'max_score': 971.924, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U971924.jpg'}, {'end': 1006.594, 'src': 'heatmap', 'start': 971.924, 'weight': 0.704, 'content': [{'end': 975.366, 'text': "so let's quickly create the graph, which will be something like vector of pair.", 'start': 971.924, 'duration': 3.442}, {'end': 976.627, 'text': 'we need to store pairs this time.', 'start': 975.366, 'duration': 1.261}, {'end': 978.909, 'text': 'so adjacency of n okay.', 'start': 976.627, 'duration': 2.282}, {'end': 982.371, 'text': 'next we go across and say ind i equal to zero, i less than n.', 'start': 978.909, 'duration': 3.462}, {'end': 985.154, 'text': 'i plus plus is something which you will do now.', 'start': 982.371, 'duration': 2.783}, {'end': 991.68, 'text': "is the next thing that i'll do is the adjacency of u, by the way, just to make your understanding better, edges of i.", 'start': 985.154, 'duration': 6.526}, {'end': 997.345, 'text': '0, because every index has a vector and the vector resembles three guys.', 'start': 991.68, 'duration': 5.665}, {'end': 999.427, 'text': 'that is the meaning of this.', 'start': 997.345, 'duration': 2.082}, {'end': 1006.594, 'text': 'so u is this v is edges of i of one and wd is on the second index.', 'start': 999.427, 'duration': 7.167}], 'summary': 'Creating a graph using vectors of pairs to store adjacency of n, and iterating through edges to assign values to u, v, and wd.', 'duration': 34.67, 'max_score': 971.924, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U971924.jpg'}, {'end': 1068.993, 'src': 'embed', 'start': 1024.358, 'weight': 1, 'content': [{'end': 1026.859, 'text': 'i need a visited array, i need a stack.', 'start': 1024.358, 'duration': 2.501}, {'end': 1028.661, 'text': 'and do i need anything else?', 'start': 1026.859, 'duration': 1.802}, {'end': 1031.881, 'text': "no, so let's quickly create the visited array.", 'start': 1028.661, 'duration': 3.22}, {'end': 1038.358, 'text': 'so i create a visited array, something like this, which is capital n equal to zero, perfect.', 'start': 1031.881, 'duration': 6.477}, {'end': 1039.239, 'text': 'uh, i need a stack.', 'start': 1038.358, 'duration': 0.881}, {'end': 1042.34, 'text': "so let's quickly create a stack as well, perfect.", 'start': 1039.239, 'duration': 3.101}, {'end': 1045.942, 'text': 'next, i need to, uh, figure out for all components.', 'start': 1042.34, 'duration': 3.602}, {'end': 1055.71, 'text': "so let's go for all components and we say if not visited of i, we go across and say okay, listen, go for the toposort.", 'start': 1045.942, 'duration': 9.768}, {'end': 1057.231, 'text': 'and in the toposort, what do we need?', 'start': 1055.71, 'duration': 1.521}, {'end': 1061.191, 'text': 'we need the node, we need the adjacency, we need the visited and we need the stack.', 'start': 1057.231, 'duration': 3.96}, {'end': 1062.832, 'text': "so this is what i'll do.", 'start': 1061.191, 'duration': 1.641}, {'end': 1064.152, 'text': "i'll get my toposort.", 'start': 1062.832, 'duration': 1.32}, {'end': 1066.853, 'text': "so now quickly write the toposort, and that's for dfs.", 'start': 1064.152, 'duration': 2.701}, {'end': 1068.993, 'text': 'you can always write whatever you wish.', 'start': 1066.853, 'duration': 2.14}], 'summary': 'Creating visited array and stack for toposort algorithm.', 'duration': 44.635, 'max_score': 1024.358, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U1024358.jpg'}, {'end': 1167.407, 'src': 'embed', 'start': 1121.203, 'weight': 5, 'content': [{'end': 1127.668, 'text': "That's very simple because we will be calling the toposort for v adjacency visited and stack.", 'start': 1121.203, 'duration': 6.465}, {'end': 1130.15, 'text': "So this is how I'll call the toposort.", 'start': 1128.629, 'duration': 1.521}, {'end': 1135.315, 'text': "So I can say once I've done this, the stack is ready and it has all the toposort elements.", 'start': 1130.491, 'duration': 4.824}, {'end': 1138.437, 'text': 'Next, step two, do the distance thing.', 'start': 1135.975, 'duration': 2.462}, {'end': 1140.459, 'text': 'Do the distance thing.', 'start': 1138.898, 'duration': 1.561}, {'end': 1147.705, 'text': 'And what do I need for doing the distance thing? I need a vector which stores all the distance elements.', 'start': 1141.18, 'duration': 6.525}, {'end': 1153.516, 'text': 'perfect. please make sure everything is initially marked as infinity.', 'start': 1149.192, 'duration': 4.324}, {'end': 1161.182, 'text': 'so i this and you can go on like i, less than n, i plus plus, and you can go as distance of i equal to infinity.', 'start': 1153.516, 'duration': 7.666}, {'end': 1163.684, 'text': 'you can call it as int max, super simple.', 'start': 1161.182, 'duration': 2.502}, {'end': 1167.407, 'text': "next, you know you have a source node and that's always zero.", 'start': 1163.684, 'duration': 3.723}], 'summary': 'Using topological sorting to create stack of elements, followed by setting up distance calculation with vector and initializing with infinity, and setting the source node to zero.', 'duration': 46.204, 'max_score': 1121.203, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U1121203.jpg'}, {'end': 1293.718, 'src': 'heatmap', 'start': 1191.443, 'weight': 4, 'content': [{'end': 1200.707, 'text': 'and you know over here intv, id dot first stores the adjacent nodes and id dot second stores the weight and i need to relax it.', 'start': 1191.443, 'duration': 9.264}, {'end': 1206.77, 'text': 'so distance of node is what it takes to reach the node and from u to v it takes weight.', 'start': 1200.707, 'duration': 6.063}, {'end': 1212.753, 'text': 'and if it is lesser than the previous uh way of reaching v, it can be infinite.', 'start': 1206.77, 'duration': 5.983}, {'end': 1213.854, 'text': 'it can be anything.', 'start': 1212.753, 'duration': 1.101}, {'end': 1218.976, 'text': 'if node plus v, it is lesser than the previous way of reaching it, i do not do anything.', 'start': 1213.854, 'duration': 5.122}, {'end': 1223.238, 'text': 'i just go across and update it to the new node.', 'start': 1218.976, 'duration': 4.262}, {'end': 1224.038, 'text': "this is what i'll do.", 'start': 1223.238, 'duration': 0.8}, {'end': 1225.679, 'text': "i'll just update it to new node.", 'start': 1224.038, 'duration': 1.641}, {'end': 1227.64, 'text': "once i've done this, i'll return the distance.", 'start': 1225.679, 'duration': 1.961}, {'end': 1234.491, 'text': "this is how simple it is and after this i'll go across and run this and see if it is fine.", 'start': 1228.4, 'duration': 6.091}, {'end': 1237.797, 'text': 'it gives me a compilation error because i think we my bad.', 'start': 1234.491, 'duration': 3.306}, {'end': 1238.358, 'text': 'it will be pushed back.', 'start': 1237.797, 'duration': 0.561}, {'end': 1240.509, 'text': "So let's quickly run this.", 'start': 1239.608, 'duration': 0.901}, {'end': 1242.071, 'text': "So I've done a slight typo.", 'start': 1241.01, 'duration': 1.061}, {'end': 1244.793, 'text': 'Over here, it will be M because number of edges.', 'start': 1242.231, 'duration': 2.562}, {'end': 1248.197, 'text': "I'll quickly compile and see if it is giving us the correct answer.", 'start': 1244.813, 'duration': 3.384}, {'end': 1251.48, 'text': 'In compilation, we see that it is giving us the correct answer.', 'start': 1249.158, 'duration': 2.322}, {'end': 1253.022, 'text': 'Will we submit? No.', 'start': 1251.901, 'duration': 1.121}, {'end': 1253.923, 'text': "Let's wait.", 'start': 1253.442, 'duration': 0.481}, {'end': 1256.425, 'text': "Let's read a couple of statements.", 'start': 1254.423, 'duration': 2.002}, {'end': 1258.708, 'text': 'So it says, find the shortest path.', 'start': 1256.826, 'duration': 1.882}, {'end': 1264.395, 'text': "But does it mention about what if we do not reach? So it doesn't mention about it.", 'start': 1259.028, 'duration': 5.367}, {'end': 1266.818, 'text': "I'll ask the problem setter to add it up.", 'start': 1264.515, 'duration': 2.303}, {'end': 1268.641, 'text': "But as of now, there's a trick.", 'start': 1267.039, 'duration': 1.602}, {'end': 1274.328, 'text': "I'll go here and I say, okay, they're expecting if it is 1E9 to see out infinity, not reachable.", 'start': 1269.101, 'duration': 5.227}, {'end': 1276.791, 'text': "They're expecting 1E9 instead of intermax.", 'start': 1274.749, 'duration': 2.042}, {'end': 1282.594, 'text': "So, I'll just assign 1E9 because what they're expecting is if it's not reachable, it should be 1E9.", 'start': 1277.412, 'duration': 5.182}, {'end': 1285.095, 'text': 'So, I just did a slight hack.', 'start': 1283.094, 'duration': 2.001}, {'end': 1286.195, 'text': 'I just checked in.', 'start': 1285.595, 'duration': 0.6}, {'end': 1288.576, 'text': "But I'll ask the problem setter to update the problem statement.", 'start': 1286.275, 'duration': 2.301}, {'end': 1289.336, 'text': "Don't worry about that.", 'start': 1288.616, 'duration': 0.72}, {'end': 1293.718, 'text': "I'll now quickly run this off and see if it is running fine.", 'start': 1290.357, 'duration': 3.361}], 'summary': 'The speaker explains the process of updating distances in a graph and addresses a compilation error, making a slight hack to handle unreachable nodes.', 'duration': 46.354, 'max_score': 1191.443, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U1191443.jpg'}, {'end': 1302.861, 'src': 'embed', 'start': 1277.412, 'weight': 8, 'content': [{'end': 1282.594, 'text': "So, I'll just assign 1E9 because what they're expecting is if it's not reachable, it should be 1E9.", 'start': 1277.412, 'duration': 5.182}, {'end': 1285.095, 'text': 'So, I just did a slight hack.', 'start': 1283.094, 'duration': 2.001}, {'end': 1286.195, 'text': 'I just checked in.', 'start': 1285.595, 'duration': 0.6}, {'end': 1288.576, 'text': "But I'll ask the problem setter to update the problem statement.", 'start': 1286.275, 'duration': 2.301}, {'end': 1289.336, 'text': "Don't worry about that.", 'start': 1288.616, 'duration': 0.72}, {'end': 1293.718, 'text': "I'll now quickly run this off and see if it is running fine.", 'start': 1290.357, 'duration': 3.361}, {'end': 1294.358, 'text': 'Okay, it is.', 'start': 1293.778, 'duration': 0.58}, {'end': 1297.459, 'text': 'So, all of these test cases do pass.', 'start': 1294.819, 'duration': 2.64}, {'end': 1299.46, 'text': 'So, we have understood the algorithm.', 'start': 1297.58, 'duration': 1.88}, {'end': 1300.841, 'text': 'We have understood the code.', 'start': 1299.9, 'duration': 0.941}, {'end': 1302.861, 'text': "Now, let's discuss the time complexity.", 'start': 1301.341, 'duration': 1.52}], 'summary': 'Code passed all test cases, time complexity discussion next.', 'duration': 25.449, 'max_score': 1277.412, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U1277412.jpg'}], 'start': 952.187, 'title': 'Graph algorithms in c++ and java', 'summary': "Covers graph creation in c++ and java, implementing topological sort algorithm, and dijkstra's algorithm implementation. it emphasizes the importance of finding topological order, discusses creating a visited array and a stack, traversing the graph using dfs, and implementing dijkstra's algorithm for finding the shortest path.", 'chapters': [{'end': 1024.358, 'start': 952.187, 'title': 'Graph creation in c++ and java', 'summary': 'Demonstrates the process of creating a graph in c++ and java, given the number of nodes, edges, and edge data, using vectors and pairs to store adjacency information and emphasizing the importance of finding the topological order.', 'duration': 72.171, 'highlights': ['The chapter demonstrates the process of creating a graph in C++ and Java, given the number of nodes, edges, and edge data, using vectors and pairs to store adjacency information.', 'Emphasizes the importance of finding the topological order.']}, {'end': 1147.705, 'start': 1024.358, 'title': 'Implementing topological sort algorithm', 'summary': 'Discusses implementing the topological sort algorithm, creating a visited array and a stack, and traversing the graph using dfs to obtain the topological ordering of the nodes and calculating distances.', 'duration': 123.347, 'highlights': ['Creating a visited array and a stack for graph traversal, no other data structures are needed.', 'Traversing the graph using DFS to obtain the topological ordering of nodes and ensuring that all components are visited.', 'Discussing the process of obtaining the topological ordering of nodes through DFS and maintaining the stack for further use.', 'Emphasizing the need for a vector to store distance elements as part of the distance calculation process.']}, {'end': 1299.46, 'start': 1149.192, 'title': "Dijkstra's algorithm implementation", 'summary': "Covers the implementation of dijkstra's algorithm for finding the shortest path, including the use of infinity as a placeholder, stack operations, relaxation of distances, and a slight hack to handle unreachable nodes, resulting in successful passing of test cases.", 'duration': 150.268, 'highlights': ["Implementing Dijkstra's algorithm for finding the shortest path. The transcript covers the implementation of Dijkstra's algorithm for finding the shortest path.", 'Initial marking of everything as infinity. The algorithm initially marks everything as infinity to signify unreachability.', 'Using stack operations to process nodes and adjacent nodes. The algorithm uses stack operations to process nodes and their adjacent nodes.', 'Relaxing distances to optimize the shortest path calculation. The algorithm relaxes distances to optimize the calculation of the shortest path.', 'Slight hack to handle unreachable nodes by assigning 1E9 instead of int max. A slight hack is used to handle unreachable nodes by assigning 1E9 instead of int max, resulting in successful passing of test cases.']}], 'duration': 347.273, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U952187.jpg', 'highlights': ['Covers graph creation in C++ and Java using vectors and pairs to store adjacency information.', 'Emphasizes the importance of finding the topological order.', 'Creating a visited array and a stack for graph traversal, no other data structures are needed.', 'Traversing the graph using DFS to obtain the topological ordering of nodes and ensuring that all components are visited.', "Implementing Dijkstra's algorithm for finding the shortest path.", "Initial marking of everything as infinity to signify unreachability in Dijkstra's algorithm.", "Using stack operations to process nodes and their adjacent nodes in Dijkstra's algorithm.", "Relaxing distances to optimize the calculation of the shortest path in Dijkstra's algorithm.", "Handling unreachable nodes by assigning 1E9 instead of int max in Dijkstra's algorithm."]}, {'end': 1586.712, 'segs': [{'end': 1339.516, 'src': 'embed', 'start': 1299.9, 'weight': 2, 'content': [{'end': 1300.841, 'text': 'We have understood the code.', 'start': 1299.9, 'duration': 0.941}, {'end': 1302.861, 'text': "Now, let's discuss the time complexity.", 'start': 1301.341, 'duration': 1.52}, {'end': 1304.402, 'text': 'Then, we will go across to the intuition.', 'start': 1302.902, 'duration': 1.5}, {'end': 1306.463, 'text': 'What is the time complexity? A toposol.', 'start': 1304.722, 'duration': 1.741}, {'end': 1307.848, 'text': 'Plain DFS.', 'start': 1307.267, 'duration': 0.581}, {'end': 1309.89, 'text': 'Whatever time the DFS takes.', 'start': 1308.188, 'duration': 1.702}, {'end': 1314.294, 'text': 'What about this? The number of nodes is what the stack will always give you.', 'start': 1310.49, 'duration': 3.804}, {'end': 1315.355, 'text': "That's for sure.", 'start': 1314.694, 'duration': 0.661}, {'end': 1318.838, 'text': 'The number of nodes is what the stack will give you, which is n.', 'start': 1315.855, 'duration': 2.983}, {'end': 1320.32, 'text': 'Into all the neighbors.', 'start': 1318.838, 'duration': 1.482}, {'end': 1321.601, 'text': 'Into all the neighbors.', 'start': 1320.94, 'duration': 0.661}, {'end': 1327.647, 'text': "So if I ask you, in total, this for loop will run for how many times? Let's go back.", 'start': 1322.161, 'duration': 5.486}, {'end': 1339.516, 'text': 'So can I say in the iPad, first run 0 will run for once, twice, thrice, four times, five times, six times, seven times, eight times.', 'start': 1328.626, 'duration': 10.89}], 'summary': 'Discussed time complexity and calculated iterations, reaching a total of eight.', 'duration': 39.616, 'max_score': 1299.9, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U1299900.jpg'}, {'end': 1377.942, 'src': 'embed', 'start': 1348.824, 'weight': 0, 'content': [{'end': 1352.667, 'text': 'two, three, four, five, six, seven, eight, which is nothing but the images.', 'start': 1348.824, 'duration': 3.843}, {'end': 1356.162, 'text': 'i say overall it will run for images.', 'start': 1353.82, 'duration': 2.342}, {'end': 1362.127, 'text': 'so n plus m is what the second loop will run.', 'start': 1356.162, 'duration': 5.965}, {'end': 1363.989, 'text': 'this is a plain dfs.', 'start': 1362.127, 'duration': 1.862}, {'end': 1368.893, 'text': 'this is plain dfs n plus e, the number of edges, which is m.', 'start': 1363.989, 'duration': 4.904}, {'end': 1370.175, 'text': 'but this is very obvious.', 'start': 1368.893, 'duration': 1.282}, {'end': 1377.942, 'text': 'right, because the stack will give you n and in total the adjacent nodes is nothing but the number of edges only.', 'start': 1370.175, 'duration': 7.767}], 'summary': 'The algorithm runs for n+m images using plain dfs for n+e edges.', 'duration': 29.118, 'max_score': 1348.824, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U1348824.jpg'}, {'end': 1513.218, 'src': 'embed', 'start': 1465.402, 'weight': 3, 'content': [{'end': 1466.503, 'text': "I'll go to 5.", 'start': 1465.402, 'duration': 1.101}, {'end': 1468.404, 'text': "I'll figure out the answer for 5.", 'start': 1466.503, 'duration': 1.901}, {'end': 1469.005, 'text': "Then I'll go to 4.", 'start': 1468.404, 'duration': 0.601}, {'end': 1470.846, 'text': 'Figure out the answer for 4.', 'start': 1469.005, 'duration': 1.841}, {'end': 1472.027, 'text': "Then I'll go to 0 and 2.", 'start': 1470.846, 'duration': 1.181}, {'end': 1472.928, 'text': 'Figure out the answer for them.', 'start': 1472.027, 'duration': 0.901}, {'end': 1474.669, 'text': "Then I'll go to 3.", 'start': 1473.368, 'duration': 1.301}, {'end': 1475.309, 'text': "Then I'll go to 1.", 'start': 1474.669, 'duration': 0.64}, {'end': 1476.17, 'text': "And I'll figure out.", 'start': 1475.309, 'duration': 0.861}, {'end': 1478.132, 'text': 'So what I did was, I moved.', 'start': 1476.47, 'duration': 1.662}, {'end': 1481.234, 'text': 'sequentially the nodes which are reachable.', 'start': 1478.792, 'duration': 2.442}, {'end': 1487.998, 'text': 'first i moved them, then this, then this, then this, then this, then this, then this.', 'start': 1481.234, 'duration': 6.764}, {'end': 1490.38, 'text': 'i moved according to reachability.', 'start': 1487.998, 'duration': 2.382}, {'end': 1492.381, 'text': 'moved according to reachability.', 'start': 1490.38, 'duration': 2.001}, {'end': 1502.848, 'text': 'so what happened was i minimized the number of steps to be go of n plus m, which is much, much better than any standard algorithm,', 'start': 1492.381, 'duration': 10.467}, {'end': 1504.549, 'text': 'because dexter takes more than this.', 'start': 1502.848, 'duration': 1.701}, {'end': 1513.218, 'text': 'the only reason it works is because we are making sure there was no one before six and we computed for six, then we did for five.', 'start': 1505.51, 'duration': 7.708}], 'summary': 'Proposed a sequential approach to minimize steps in node traversal.', 'duration': 47.816, 'max_score': 1465.402, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U1465402.jpg'}, {'end': 1567.104, 'src': 'embed', 'start': 1539.954, 'weight': 6, 'content': [{'end': 1544.676, 'text': 'So I started with a very small and then I expanded it to 2.', 'start': 1539.954, 'duration': 4.722}, {'end': 1546.197, 'text': 'Then I expanded it to 3 and so on.', 'start': 1544.676, 'duration': 1.521}, {'end': 1547.597, 'text': 'That is how we will do it.', 'start': 1546.637, 'duration': 0.96}, {'end': 1550.338, 'text': 'So in short, the intuition is very straightforward.', 'start': 1548.258, 'duration': 2.08}, {'end': 1553.76, 'text': "If I'm reaching a node, I know all the previous nodes have their answers.", 'start': 1550.739, 'duration': 3.021}, {'end': 1556.221, 'text': 'right. that is the simple intuition.', 'start': 1554.46, 'duration': 1.761}, {'end': 1557.481, 'text': 'we still have a problem.', 'start': 1556.221, 'duration': 1.26}, {'end': 1560.442, 'text': "i'll leave a stack overflow link on the description.", 'start': 1557.481, 'duration': 2.961}, {'end': 1562.802, 'text': 'you can check it out or the answer is given over there.', 'start': 1560.442, 'duration': 2.36}, {'end': 1567.104, 'text': 'you can read it again and again, but i think it is more or less clear to you now.', 'start': 1562.802, 'duration': 4.302}], 'summary': 'Incremental expansion from 1 to 3, intuitive approach for reaching nodes and addressing stack overflow issues.', 'duration': 27.15, 'max_score': 1539.954, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U1539954.jpg'}], 'start': 1299.9, 'title': 'Time and space complexity', 'summary': 'Explains the time complexity of a plain depth-first search (dfs) algorithm, with the inner loop running for n+m times, where n is the number of nodes and m is the number of edges and also covers understanding topological sorting for finding the shortest path, which minimizes the number of steps to be taken in a directed graph, better than standard algorithms like dexter.', 'chapters': [{'end': 1377.942, 'start': 1299.9, 'title': 'Time complexity of plain dfs', 'summary': 'Explains the time complexity of a plain depth-first search (dfs) algorithm, with the inner loop running for n+m times, where n is the number of nodes and m is the number of edges.', 'duration': 78.042, 'highlights': ['The inner loop of the DFS algorithm runs for n+m times, where n is the number of nodes and m is the number of edges.', 'The stack in the DFS algorithm always gives the number of nodes, which is n.', 'The total number of times the adjacent nodes for loop runs is n+m, where n is the number of nodes and m is the number of edges.']}, {'end': 1586.712, 'start': 1377.942, 'title': 'Understanding topological sorting for shortest path', 'summary': 'Explains the intuition behind using topological sorting for finding the shortest path, emphasizing that it minimizes the number of steps to be taken in a directed graph, which is much better than standard algorithms like dexter.', 'duration': 208.77, 'highlights': ['Topological sorting minimizes number of steps in a directed graph, better than standard algorithms like dexter. By using topological sorting, the number of steps to be taken is minimized to n + m, which is much better than standard algorithms like dexter.', 'Sequentially moving nodes according to reachability The nodes are moved sequentially according to their reachability, ensuring that the answers of previous nodes are known before computing for the current node.', "Intuition: Knowing previous nodes' answers when reaching a node When reaching a node, it is ensured that all the previous nodes have their answers computed, which simplifies the process of finding the shortest path."]}], 'duration': 286.812, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ZUFQfFaU-8U/pics/ZUFQfFaU-8U1299900.jpg', 'highlights': ['The inner loop of the DFS algorithm runs for n+m times, where n is the number of nodes and m is the number of edges.', 'The total number of times the adjacent nodes for loop runs is n+m, where n is the number of nodes and m is the number of edges.', 'The stack in the DFS algorithm always gives the number of nodes, which is n.', 'Topological sorting minimizes number of steps in a directed graph, better than standard algorithms like dexter.', 'By using topological sorting, the number of steps to be taken is minimized to n + m, which is much better than standard algorithms like dexter.', 'Sequentially moving nodes according to reachability The nodes are moved sequentially according to their reachability, ensuring that the answers of previous nodes are known before computing for the current node.', "Intuition: Knowing previous nodes' answers when reaching a node When reaching a node, it is ensured that all the previous nodes have their answers computed, which simplifies the process of finding the shortest path."]}], 'highlights': ["The process involves declaring a distance array and marking it with infinity, then setting the source node's distance to zero, and subsequently removing nodes from the stack while updating their distances.", 'The key step in relaxing the edges involves updating the distances of the nodes while taking them out of the stack, ensuring the correct distances are maintained for optimal pathfinding.', "The chapter discusses the process of finding the shortest distance from a source node to all other nodes in a graph using Dijkstra's algorithm. Demonstrates the application of Dijkstra's algorithm to find the shortest path in a graph.", 'Detailed step-by-step explanations and examples of updating the distance array for each node are provided. Provides detailed explanations and examples of the step-by-step process of updating the distance array for each node in the graph.', 'The algorithm involves identifying adjacent nodes and calculating the distance required to reach each node from the source. Explains the process of identifying adjacent nodes and calculating the distance required to reach each node from the source node.', 'The approach combines topological sort with edge relaxation to solve the problem, marking a slight variation from the traditional topological sort algorithm.', 'The problem statement is to find the shortest path from the source (0) to all other nodes in a directed acyclic graph (DAG), with the source always being 0. This sets the context for the problem and outlines the specific objective of determining the shortest paths.', 'The graph representation uses pairs to store the adjacency list, with each pair indicating the neighboring node and the corresponding edge weight. This explains the use of pairs to represent the adjacency list, providing insight into the data structure used for graph representation.', 'The toposort can be executed using either the DFS or BFS method.', 'The step one of the algorithm involves performing a toposort on the graph using either the DFS or BFS method.', 'The interviewer may ask the question with any given source, requiring flexibility in choosing the source.', 'The process involves calling DFS for each unvisited node, such as in the given example, where DFS is called for nodes 0, 1, and 3.', 'The DFS method uses a stack data structure to store the toposort, putting each node into the stack after completing its DFS (Depth First Search) traversal.', 'The stack will store the topo sort once all the dfs calls have been completed.', 'The valid topological sort is 6, 5, 4, 2, 0, 1, 3, based on the completed DFS calls.', 'Covers graph creation in C++ and Java using vectors and pairs to store adjacency information.', 'Emphasizes the importance of finding the topological order.', 'Creating a visited array and a stack for graph traversal, no other data structures are needed.', 'Traversing the graph using DFS to obtain the topological ordering of nodes and ensuring that all components are visited.', "Implementing Dijkstra's algorithm for finding the shortest path.", "Initial marking of everything as infinity to signify unreachability in Dijkstra's algorithm.", "Using stack operations to process nodes and their adjacent nodes in Dijkstra's algorithm.", "Relaxing distances to optimize the calculation of the shortest path in Dijkstra's algorithm.", "Handling unreachable nodes by assigning 1E9 instead of int max in Dijkstra's algorithm.", 'The inner loop of the DFS algorithm runs for n+m times, where n is the number of nodes and m is the number of edges.', 'The total number of times the adjacent nodes for loop runs is n+m, where n is the number of nodes and m is the number of edges.', 'The stack in the DFS algorithm always gives the number of nodes, which is n.', 'Topological sorting minimizes number of steps in a directed graph, better than standard algorithms like dexter.', 'By using topological sorting, the number of steps to be taken is minimized to n + m, which is much better than standard algorithms like dexter.', 'Sequentially moving nodes according to reachability The nodes are moved sequentially according to their reachability, ensuring that the answers of previous nodes are known before computing for the current node.', "Intuition: Knowing previous nodes' answers when reaching a node When reaching a node, it is ensured that all the previous nodes have their answers computed, which simplifies the process of finding the shortest path."]}