title
6.13 Dijkstra Algorithm | Single Source Shortest Path| Greedy Method

description
In this video I have explained Dijkstra's Algorithm with some Examples. It is Single Source Shortest Path Algorithm and use Greedy Method. DSA Full Course: https: https://www.youtube.com/playlist?list=PLdo5W4Nhv31bbKJzrsKfMpo_grxuLl8LU ****************************************** More Playlists: C Programming Course: https://www.youtube.com/playlist?list=PLdo5W4Nhv31a8UcMN9-35ghv8qyFWD9_S C++ Programming: https://www.youtube.com/playlist?list=PLdo5W4Nhv31YU5Wx1dopka58teWP9aCee Python Full Course: https://www.youtube.com/playlist?list=PLdo5W4Nhv31bZSiqiOL5ta39vSnBxpOPT Printing Pattern in C: https://www.youtube.com/playlist?list=PLdo5W4Nhv31Yu1igxTE2x0aeShbKtVcCy DAA Course: https://www.youtube.com/playlist?list=PLdo5W4Nhv31ZTn2P9vF02bkb3SC8uiUUn Placement Series: https://www.youtube.com/playlist?list=PLdo5W4Nhv31YvlDpJhvOYbM9Ap8UypgEy Dynamic Programming: https://www.youtube.com/playlist?list=PLdo5W4Nhv31aBrJE1WS4MR9LRfbmZrAQu Operating Systems: //www.youtube.com/playlist?list=PLdo5W4Nhv31a5ucW_S1K3-x6ztBRD-PNa DBMS: https://www.youtube.com/playlist?list=PLdo5W4Nhv31b33kF46f9aFjoJPOkdlsRc ******************************************** Connect & Contact Me: Facebook: https://www.facebook.com/Jennys-Lectures-CSIT-Netjrf-316814368950701/ Quora: https://www.quora.com/profile/Jayanti-Khatri-Lamba Instagram: https://www.instagram.com/jayantikhatrilamba/ #dijkstra #jennyslectures #datastructures

detail
{'title': '6.13 Dijkstra Algorithm | Single Source Shortest Path| Greedy Method', 'heatmap': [{'end': 502.783, 'start': 454.42, 'weight': 0.714}, {'end': 1352.092, 'start': 1326.361, 'weight': 0.707}, {'end': 1602.116, 'start': 1514.423, 'weight': 0.755}], 'summary': "Covers shortest path algorithms, explaining dijkstra's algorithm for finding the shortest path in a graph, discussing its drawbacks and limitations, and showcasing its application with specific examples and calculations, achieving a shortest distance of 9 from a to d via c and b.", 'chapters': [{'end': 187.774, 'segs': [{'end': 55.111, 'src': 'embed', 'start': 0.529, 'weight': 0, 'content': [{'end': 1.67, 'text': 'Hi guys, welcome back.', 'start': 0.529, 'duration': 1.141}, {'end': 4.193, 'text': "Today's topic is diastereo algorithm.", 'start': 1.71, 'duration': 2.483}, {'end': 11.519, 'text': 'So in this video I am going to discuss with you the working principle of diastereo algorithm and then what are the drawbacks of this algorithm.', 'start': 5.013, 'duration': 6.506}, {'end': 17.724, 'text': 'So diastereo algorithm is basically single source shortest path problem.', 'start': 12.56, 'duration': 5.164}, {'end': 27.586, 'text': 'singles single source shortest path problem see the name suggests single source.', 'start': 21.644, 'duration': 5.942}, {'end': 30.987, 'text': 'in this algorithm, one source is given.', 'start': 27.586, 'duration': 3.401}, {'end': 38.59, 'text': 'you are supposed to ask to find out the shortest path, maybe, and you are supposed to consider maybe zero as a source, vertex,', 'start': 30.987, 'duration': 7.603}, {'end': 44.012, 'text': 'and from zero you are supposed to find out the shortest path to all the vertices.', 'start': 38.59, 'duration': 5.422}, {'end': 55.111, 'text': 'or maybe you are supposed to, you know, ask 2 is the source and you are supposed to find out the shortest path from 2 to 1,, 2 to 4, 2 to 8, 2 to 5,', 'start': 44.012, 'duration': 11.099}], 'summary': 'Diastereo algorithm is a single source shortest path problem, finding shortest paths from a given source to all vertices.', 'duration': 54.582, 'max_score': 0.529, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/smHnz2RHJBY/pics/smHnz2RHJBY529.jpg'}, {'end': 100.478, 'src': 'embed', 'start': 75.089, 'weight': 3, 'content': [{'end': 87.297, 'text': "okay, see, suppose this is your graph and you're supposed to find out the shortest path, and source vertex that is given to you is zero,", 'start': 75.089, 'duration': 12.208}, {'end': 88.858, 'text': 'zero as a source vertex.', 'start': 87.297, 'duration': 1.561}, {'end': 94.593, 'text': 'maybe you can consider 5 as a source vertex and start your algorithm.', 'start': 89.929, 'duration': 4.664}, {'end': 98.337, 'text': 'you can consider 8 as source vertex, or maybe in question, you are given 6.', 'start': 94.593, 'duration': 3.744}, {'end': 100.478, 'text': 'consider 6 as a source vertex.', 'start': 98.337, 'duration': 2.141}], 'summary': 'Finding the shortest path from different source vertices in a graph.', 'duration': 25.389, 'max_score': 75.089, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/smHnz2RHJBY/pics/smHnz2RHJBY75089.jpg'}, {'end': 165.719, 'src': 'embed', 'start': 130.44, 'weight': 2, 'content': [{'end': 132.662, 'text': 'that is why i am starting from this.', 'start': 130.44, 'duration': 2.222}, {'end': 135.745, 'text': 'uh, i am starting our algorithm from this vertex only.', 'start': 132.662, 'duration': 3.083}, {'end': 150.629, 'text': 'so, from zero to zero, distance is zero, And at first step, the distance of all other vertices would be infinity, infinity, infinity, like that.', 'start': 135.745, 'duration': 14.884}, {'end': 152.71, 'text': "we don't know what is the distance?", 'start': 150.629, 'duration': 2.081}, {'end': 154.171, 'text': 'what is the shortest path?', 'start': 152.71, 'duration': 1.461}, {'end': 156.333, 'text': 'okay, now, let us start.', 'start': 154.171, 'duration': 2.162}, {'end': 165.719, 'text': 'we are going to start from zero from zero to how many vertices are directly connected this, this one and this four,', 'start': 156.333, 'duration': 9.386}], 'summary': 'Algorithm initializes distances and starts from vertex zero.', 'duration': 35.279, 'max_score': 130.44, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/smHnz2RHJBY/pics/smHnz2RHJBY130440.jpg'}], 'start': 0.529, 'title': 'Shortest path algorithms', 'summary': 'Provides an overview of the diastereo algorithm, a single source shortest path problem, and its drawbacks, as well as the application of a shortest path algorithm using a graph and source vertex to calculate distances and determine the shortest path.', 'chapters': [{'end': 75.089, 'start': 0.529, 'title': 'Diastereo algorithm overview', 'summary': 'Discusses the working principle of the diastereo algorithm, which is a single source shortest path problem, and highlights its drawbacks.', 'duration': 74.56, 'highlights': ['The diastereo algorithm is a single source shortest path problem, where the goal is to find the shortest path from one given source vertex to all other vertices.', 'The algorithm involves determining the shortest path from a specified source vertex to all other vertices, and it can be applied with different source vertices, such as 0 or 2, to find their respective shortest paths.', 'The chapter also delves into the drawbacks of the diastereo algorithm, which will be elaborated further in the discussion.']}, {'end': 187.774, 'start': 75.089, 'title': 'Shortest path algorithm', 'summary': 'Discusses the application of a shortest path algorithm using a graph and source vertex, highlighting the process of calculating distances and determining the shortest path.', 'duration': 112.685, 'highlights': ['The process of calculating distances from the source vertex and determining the shortest path The algorithm involves calculating distances from the source vertex (0) to other vertices and determining the shortest path, with initial distances set as infinity and then iteratively updating based on the connected vertices.', 'Consideration of different source vertices and their impact on the algorithm The discussion emphasizes the consideration of various source vertices (e.g., 5, 8, 6) and their impact on the algorithm, showcasing the flexibility in selecting the source vertex for the shortest path calculation.', 'Initial distance setting and update iterations during the algorithm The initial step involves setting distances from the source vertex (0) as zero and others as infinity, then iteratively updating the distances based on the connected vertices to determine the shortest path.']}], 'duration': 187.245, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/smHnz2RHJBY/pics/smHnz2RHJBY529.jpg', 'highlights': ['The diastereo algorithm is a single source shortest path problem, where the goal is to find the shortest path from one given source vertex to all other vertices.', 'The algorithm involves determining the shortest path from a specified source vertex to all other vertices, and it can be applied with different source vertices, such as 0 or 2, to find their respective shortest paths.', 'The process of calculating distances from the source vertex and determining the shortest path The algorithm involves calculating distances from the source vertex (0) to other vertices and determining the shortest path, with initial distances set as infinity and then iteratively updating based on the connected vertices.', 'Consideration of different source vertices and their impact on the algorithm The discussion emphasizes the consideration of various source vertices (e.g., 5, 8, 6) and their impact on the algorithm, showcasing the flexibility in selecting the source vertex for the shortest path calculation.']}, {'end': 426.479, 'segs': [{'end': 334.061, 'src': 'embed', 'start': 292.398, 'weight': 0, 'content': [{'end': 296.879, 'text': 'This is the main formula to calculate the shortest distance.', 'start': 292.398, 'duration': 4.481}, {'end': 301.3, 'text': 'Okay Now again find out from 0 to 4.', 'start': 297.458, 'duration': 3.842}, {'end': 303.382, 'text': 'Here this one is 0 now.', 'start': 301.3, 'duration': 2.082}, {'end': 307.704, 'text': 'Sorry 0 is u and now v is this 4.', 'start': 303.822, 'duration': 3.882}, {'end': 311.607, 'text': 'Okay Now from 0 to 4.', 'start': 307.704, 'duration': 3.903}, {'end': 313.928, 'text': 'What is the distance? Distance of u is 0.', 'start': 311.607, 'duration': 2.321}, {'end': 319.212, 'text': '0 plus cost of this u to v edges 8.', 'start': 313.928, 'duration': 5.284}, {'end': 320.933, 'text': '0 plus 8 is 8.', 'start': 319.212, 'duration': 1.721}, {'end': 322.333, 'text': 'And 8 is less than infinity.', 'start': 320.933, 'duration': 1.4}, {'end': 328.959, 'text': 'That is why we update it and we will write here 8.', 'start': 322.393, 'duration': 6.566}, {'end': 334.061, 'text': 'okay, now, this vertex is now selected.', 'start': 328.959, 'duration': 5.102}], 'summary': 'Calculating shortest distance from vertex 0 to 4, updating to 8.', 'duration': 41.663, 'max_score': 292.398, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/smHnz2RHJBY/pics/smHnz2RHJBY292398.jpg'}, {'end': 426.479, 'src': 'embed', 'start': 361.258, 'weight': 1, 'content': [{'end': 364.659, 'text': 'every other distance is infinity, infinity and infinity.', 'start': 361.258, 'duration': 3.401}, {'end': 367.28, 'text': 'now select the shortest distance.', 'start': 364.659, 'duration': 2.621}, {'end': 369.62, 'text': 'shortest distance out of these is 4.', 'start': 367.28, 'duration': 2.34}, {'end': 373.481, 'text': 'okay, now, we will select this vertex.', 'start': 369.62, 'duration': 3.861}, {'end': 378.322, 'text': 'this vertex is now selected.', 'start': 373.481, 'duration': 4.841}, {'end': 385.309, 'text': 'okay, now, see, this vertex is now selected.', 'start': 378.322, 'duration': 6.987}, {'end': 396.175, 'text': 'from this vertex, we can update this distance from 1 to 2, we can update from 1 to 4 and we can go from 1 to 0, but we will not update this distance.', 'start': 385.309, 'duration': 10.866}, {'end': 396.555, 'text': 'why so?', 'start': 396.175, 'duration': 0.38}, {'end': 398.496, 'text': 'because 0 is already selected.', 'start': 396.555, 'duration': 1.941}, {'end': 402.919, 'text': 'so once a vertex is already visited or selected, we will not update the distance of that vertex.', 'start': 398.496, 'duration': 4.423}, {'end': 413.808, 'text': 'okay, so from 1, we will update this distance and this distance, and when you will update, if this du plus cost is less than then,', 'start': 403.539, 'duration': 10.269}, {'end': 415.449, 'text': 'only you will update now.', 'start': 413.808, 'duration': 1.641}, {'end': 419.072, 'text': 'find out from 1 to 2.', 'start': 415.449, 'duration': 3.623}, {'end': 423.956, 'text': 'now. in this case this is u and this one is v.', 'start': 419.072, 'duration': 4.884}, {'end': 426.479, 'text': 'now find out this distance.', 'start': 423.956, 'duration': 2.523}], 'summary': 'Finding shortest distance, vertex selection, and distance updating with 4 as the shortest distance.', 'duration': 65.221, 'max_score': 361.258, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/smHnz2RHJBY/pics/smHnz2RHJBY361258.jpg'}], 'start': 187.774, 'title': 'Shortest path in graphs', 'summary': 'Explains the shortest distance formula and algorithm for finding the shortest path in a graph, emphasizing distance calculation and shortest path selection based on specific examples and provided distances.', 'chapters': [{'end': 334.061, 'start': 187.774, 'title': 'Shortest distance formula', 'summary': 'Explains the formula for calculating the shortest distance between vertices in a graph, using an example with specific distances and the comparison of distances to update the shortest path.', 'duration': 146.287, 'highlights': ['The main formula for calculating the shortest distance is distance of u plus cost of u to v, which is used to update the distance of v if it is less than the current distance (e.g., 0 + 4 < ∞).', 'The example demonstrates the application of the formula by updating the distances from vertex 0 to vertex 1 (from ∞ to 4) and from vertex 0 to vertex 4 (from ∞ to 8).', 'The concept of infinity is used to represent unknown or unvisited vertices, and the comparison of distances with infinity determines the updating of the shortest path distances.']}, {'end': 426.479, 'start': 334.061, 'title': 'Shortest path algorithm', 'summary': 'Explains the shortest path algorithm using a selected vertex to find the shortest distances, with an emphasis on updating distances and selecting the shortest path based on the provided distances.', 'duration': 92.418, 'highlights': ['The algorithm selects a vertex and identifies the shortest distances to other vertices, with the shortest distance being 4.', 'The process involves updating distances from the selected vertex to other vertices while ensuring that distances are only updated if the new distance is less than the existing one.', 'The concept of not updating the distance to a vertex that has already been selected is emphasized.']}], 'duration': 238.705, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/smHnz2RHJBY/pics/smHnz2RHJBY187774.jpg', 'highlights': ['The main formula for calculating the shortest distance is distance of u plus cost of u to v, which is used to update the distance of v if it is less than the current distance (e.g., 0 + 4 < ∞).', 'The algorithm selects a vertex and identifies the shortest distances to other vertices, with the shortest distance being 4.', 'The example demonstrates the application of the formula by updating the distances from vertex 0 to vertex 1 (from ∞ to 4) and from vertex 0 to vertex 4 (from ∞ to 8).', 'The process involves updating distances from the selected vertex to other vertices while ensuring that distances are only updated if the new distance is less than the existing one.', 'The concept of infinity is used to represent unknown or unvisited vertices, and the comparison of distances with infinity determines the updating of the shortest path distances.', 'The concept of not updating the distance to a vertex that has already been selected is emphasized.']}, {'end': 1014.952, 'segs': [{'end': 502.783, 'src': 'heatmap', 'start': 454.42, 'weight': 0.714, 'content': [{'end': 458.463, 'text': 'Okay Like this we will find out all other distances.', 'start': 454.42, 'duration': 4.043}, {'end': 462.005, 'text': 'Now from this to this find out.', 'start': 459.583, 'duration': 2.422}, {'end': 464.286, 'text': 'Distance of v is 4.', 'start': 463.185, 'duration': 1.101}, {'end': 468.109, 'text': '4 plus 11 is 15.', 'start': 464.286, 'duration': 3.823}, {'end': 471.311, 'text': 'And this distance of v is 8.', 'start': 468.109, 'duration': 3.202}, {'end': 473.732, 'text': 'Okay But 8 is less than this 15.', 'start': 471.311, 'duration': 2.421}, {'end': 476.214, 'text': 'So we will not update this distance.', 'start': 473.732, 'duration': 2.482}, {'end': 481.863, 'text': 'because if this plus is less than du dv, then only we will update this.', 'start': 477.099, 'duration': 4.764}, {'end': 486.326, 'text': 'but 11 plus 4, 15, 15 is greater than 8, then we will not update this one.', 'start': 481.863, 'duration': 4.463}, {'end': 488.247, 'text': 'okay, now, this is already selected.', 'start': 486.326, 'duration': 1.921}, {'end': 489.428, 'text': '0 is already selected.', 'start': 488.247, 'duration': 1.181}, {'end': 494.652, 'text': 'we will leave these nodes now out of remaining nodes.', 'start': 489.428, 'duration': 5.224}, {'end': 496.653, 'text': 'which node is having the shortest distance?', 'start': 494.652, 'duration': 2.001}, {'end': 502.783, 'text': '8, infinity, infinity, infinity infinity 12 and infinity 8 is the shortest.', 'start': 496.653, 'duration': 6.13}], 'summary': "Finding shortest distance using dijkstra's algorithm, v distance is 8.", 'duration': 48.363, 'max_score': 454.42, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/smHnz2RHJBY/pics/smHnz2RHJBY454420.jpg'}, {'end': 595.648, 'src': 'embed', 'start': 566.673, 'weight': 0, 'content': [{'end': 569.645, 'text': 'okay, this one is 15.', 'start': 566.673, 'duration': 2.972}, {'end': 571.487, 'text': 'okay, now, we have already updated.', 'start': 569.645, 'duration': 1.842}, {'end': 574.269, 'text': 'now this one is selected.', 'start': 571.487, 'duration': 2.782}, {'end': 575.451, 'text': 'this one and this one.', 'start': 574.269, 'duration': 1.182}, {'end': 584.259, 'text': 'now, leave these nodes and out of these remaining nodes, which node is having the shortest distance 9, 15, 12, infinity, infinity, infinity.', 'start': 575.451, 'duration': 8.808}, {'end': 586.021, 'text': '9 is the shortest one.', 'start': 584.259, 'duration': 1.762}, {'end': 587.722, 'text': 'then we will select this 9.', 'start': 586.021, 'duration': 1.701}, {'end': 590.525, 'text': 'now, 5 is selected.', 'start': 587.722, 'duration': 2.803}, {'end': 592.066, 'text': 'vertex from 5.', 'start': 590.525, 'duration': 1.541}, {'end': 594.308, 'text': 'we can update 5 to 6.', 'start': 592.066, 'duration': 2.242}, {'end': 595.648, 'text': '5 to 8 distance.', 'start': 594.308, 'duration': 1.34}], 'summary': 'Finding shortest distance nodes: 9, 5, updating distances.', 'duration': 28.975, 'max_score': 566.673, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/smHnz2RHJBY/pics/smHnz2RHJBY566673.jpg'}, {'end': 957.353, 'src': 'embed', 'start': 894.361, 'weight': 1, 'content': [{'end': 900.725, 'text': 'What is the shortest distance from 0 to 8? Then the answer would be 14.', 'start': 894.361, 'duration': 6.364}, {'end': 904.328, 'text': 'What is the shortest distance from 0 to 6? That is 11.', 'start': 900.725, 'duration': 3.603}, {'end': 906.269, 'text': 'Shortest distance from 0 to 7? That is 21.', 'start': 904.328, 'duration': 1.941}, {'end': 907.53, 'text': 'From 0 to 5? 9.', 'start': 906.269, 'duration': 1.261}, {'end': 909.171, 'text': 'From 0 to 4? We have 8.', 'start': 907.53, 'duration': 1.641}, {'end': 915.756, 'text': 'From 0 to 1? We have 9.', 'start': 909.171, 'duration': 6.585}, {'end': 921.44, 'text': 'From 0 to 2, we have shortest distance is this, 12.', 'start': 915.756, 'duration': 5.684}, {'end': 923.923, 'text': 'So, this is the working principle of Dijkstra algorithm.', 'start': 921.44, 'duration': 2.483}, {'end': 930.528, 'text': 'Now, see this Dijkstra algorithm works on undirected graph and directed graph as well.', 'start': 923.983, 'duration': 6.545}, {'end': 935.852, 'text': 'Okay Now, we will take one more example of directed graph.', 'start': 930.888, 'duration': 4.964}, {'end': 944.765, 'text': 'Okay, now let us say we have this graph,', 'start': 936.393, 'duration': 8.372}, {'end': 954.731, 'text': 'which one is directed and weighted graph and we are supposed to find out the shortest path from the source vertex and source vertex is a to all other vertices.', 'start': 944.765, 'duration': 9.966}, {'end': 957.353, 'text': 'okay, let us suppose a is source vertex.', 'start': 954.731, 'duration': 2.622}], 'summary': 'Demonstration of dijkstra algorithm for finding shortest distances in graphs.', 'duration': 62.992, 'max_score': 894.361, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/smHnz2RHJBY/pics/smHnz2RHJBY894361.jpg'}], 'start': 426.479, 'title': "Dijkstra's algorithm for shortest paths", 'summary': "Explains the implementation of dijkstra's algorithm to find the shortest distances in a weighted graph, demonstrating the process and criteria for updating distances, and showcasing the working principle and application on a graph.", 'chapters': [{'end': 533.311, 'start': 426.479, 'title': 'Shortest path algorithm', 'summary': "Explains the shortest path algorithm using dijkstra's algorithm to find the shortest distances from a given source node to all other nodes in a weighted graph, with an example demonstrating the process and criteria for updating distances.", 'duration': 106.832, 'highlights': ['The algorithm involves iteratively updating the shortest distance from the source node to all other nodes based on the current minimum distance found, with the distances of the neighboring nodes being compared and updated accordingly.', "Nodes with the shortest distance are selected and their neighboring nodes' distances are updated if the new calculated distance is less than the current distance, until all nodes are visited and the shortest distances are determined.", "The process ensures that the shortest path from the source node to all other nodes in the graph is efficiently calculated, with the example demonstrating the comparison and updating of distances based on the algorithm's criteria."]}, {'end': 1014.952, 'start': 533.311, 'title': 'Dijkstra algorithm on graph', 'summary': 'Describes the dijkstra algorithm implementation on a graph, showcasing the shortest distances from the source vertex to all other vertices and the working principle of the algorithm.', 'duration': 481.641, 'highlights': ['The shortest distance from 0 to 6 is 11. The algorithm determines the shortest distance from 0 to 6 as 11, showcasing the effectiveness of the Dijkstra algorithm.', 'The shortest distance from 0 to 8 is 14. The algorithm calculates the shortest distance from 0 to 8 as 14, demonstrating the successful application of the Dijkstra algorithm.', 'The Dijkstra algorithm works on undirected and directed graphs. The chapter emphasizes that the Dijkstra algorithm is applicable to both undirected and directed graphs, highlighting its versatility and broad utility.']}], 'duration': 588.473, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/smHnz2RHJBY/pics/smHnz2RHJBY426479.jpg', 'highlights': ['The algorithm involves iteratively updating the shortest distance from the source node to all other nodes based on the current minimum distance found, with the distances of the neighboring nodes being compared and updated accordingly.', "The process ensures that the shortest path from the source node to all other nodes in the graph is efficiently calculated, with the example demonstrating the comparison and updating of distances based on the algorithm's criteria.", 'The Dijkstra algorithm works on undirected and directed graphs. The chapter emphasizes that the Dijkstra algorithm is applicable to both undirected and directed graphs, highlighting its versatility and broad utility.', 'The shortest distance from 0 to 6 is 11. The algorithm determines the shortest distance from 0 to 6 as 11, showcasing the effectiveness of the Dijkstra algorithm.', "Nodes with the shortest distance are selected and their neighboring nodes' distances are updated if the new calculated distance is less than the current distance, until all nodes are visited and the shortest distances are determined."]}, {'end': 1620.954, 'segs': [{'end': 1365.847, 'src': 'heatmap', 'start': 1326.361, 'weight': 0, 'content': [{'end': 1329.362, 'text': 'Previously And 13 is less than this 14.', 'start': 1326.361, 'duration': 3.001}, {'end': 1334.844, 'text': 'So we will update here 13.', 'start': 1329.362, 'duration': 5.482}, {'end': 1338.246, 'text': 'Now can you update this distance? E.', 'start': 1334.844, 'duration': 3.402}, {'end': 1339.987, 'text': 'We have selected this E.', 'start': 1338.246, 'duration': 1.741}, {'end': 1342.248, 'text': 'Can you update E to B? E to B.', 'start': 1339.987, 'duration': 2.261}, {'end': 1343.048, 'text': 'No There is no edge.', 'start': 1342.248, 'duration': 0.8}, {'end': 1348.929, 'text': 'Then we will write as it is here 8.', 'start': 1343.608, 'duration': 5.321}, {'end': 1352.092, 'text': 'Now we have only two vertices which are unvisited.', 'start': 1348.929, 'duration': 3.163}, {'end': 1357.378, 'text': 'Out of these two which one is having minimum distance factor that is 8.', 'start': 1352.573, 'duration': 4.805}, {'end': 1361.162, 'text': 'We will select this 8 and the vertex is B.', 'start': 1357.378, 'duration': 3.784}, {'end': 1362.603, 'text': 'B would be selected.', 'start': 1361.162, 'duration': 1.441}, {'end': 1365.847, 'text': 'Then from B we can update only this B to D.', 'start': 1363.404, 'duration': 2.443}], 'summary': 'Updating distances between vertices, selecting minimum distance factor of 8, and updating vertex b to d.', 'duration': 70.862, 'max_score': 1326.361, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/smHnz2RHJBY/pics/smHnz2RHJBY1326361.jpg'}, {'end': 1620.954, 'src': 'heatmap', 'start': 1514.423, 'weight': 2, 'content': [{'end': 1516.739, 'text': "I'll go here only Okay.", 'start': 1514.423, 'duration': 2.316}, {'end': 1518.72, 'text': 'And this has been changed.', 'start': 1517.359, 'duration': 1.361}, {'end': 1524.463, 'text': 'See, in this point it was 13 and after that it has changed to 19.', 'start': 1519.321, 'duration': 5.142}, {'end': 1535.109, 'text': 'So in this case, if this has been changed, then we will check in this row which vertices has been selected?', 'start': 1524.463, 'duration': 10.646}, {'end': 1537.45, 'text': 'Which vertices has been selected? This one.', 'start': 1535.169, 'duration': 2.281}, {'end': 1539.992, 'text': 'And this one is what? B.', 'start': 1537.81, 'duration': 2.182}, {'end': 1541.092, 'text': 'B has been selected.', 'start': 1539.992, 'duration': 1.1}, {'end': 1544.314, 'text': 'Okay Pointer would be here only.', 'start': 1541.532, 'duration': 2.782}, {'end': 1548.836, 'text': "Now I'll write here suppose B.", 'start': 1545.754, 'duration': 3.082}, {'end': 1549.817, 'text': 'B has been selected.', 'start': 1548.836, 'duration': 0.981}, {'end': 1553.359, 'text': "Then we'll go one step backward.", 'start': 1550.497, 'duration': 2.862}, {'end': 1556.001, 'text': 'Here 8 only.', 'start': 1555.161, 'duration': 0.84}, {'end': 1557.742, 'text': 'Okay No problem.', 'start': 1556.762, 'duration': 0.98}, {'end': 1561.945, 'text': "Jab tak ye value same aayegi you'll move one step backward.", 'start': 1558.303, 'duration': 3.642}, {'end': 1564.427, 'text': 'Jaise hi value change hogi.', 'start': 1561.985, 'duration': 2.442}, {'end': 1566.769, 'text': 'At that point you have to do something.', 'start': 1565.008, 'duration': 1.761}, {'end': 1568.73, 'text': 'Now go one step backward.', 'start': 1567.329, 'duration': 1.401}, {'end': 1569.891, 'text': 'Here only.', 'start': 1569.411, 'duration': 0.48}, {'end': 1574.89, 'text': 'It is 10, but the next step, it was eight.', 'start': 1571.149, 'duration': 3.741}, {'end': 1576.931, 'text': 'So this has been changed here only.', 'start': 1575.271, 'duration': 1.66}, {'end': 1587.235, 'text': 'Okay Now in this row, where the value has changed, in this row, which vertex has been selected, that is this one, 5, C.', 'start': 1577.331, 'duration': 9.904}, {'end': 1588.235, 'text': 'C has been selected.', 'start': 1587.235, 'duration': 1}, {'end': 1592.437, 'text': "Then you'll write here C.", 'start': 1589.116, 'duration': 3.321}, {'end': 1594.197, 'text': 'Pointer would be here only.', 'start': 1592.437, 'duration': 1.76}, {'end': 1597.219, 'text': 'Now go one step backward.', 'start': 1594.938, 'duration': 2.281}, {'end': 1602.116, 'text': 'Okay Here it was infinity and here it has changed.', 'start': 1598.139, 'duration': 3.977}, {'end': 1604.018, 'text': 'The same step has changed.', 'start': 1602.156, 'duration': 1.862}, {'end': 1606.981, 'text': 'So you will check in this row which vertices has been selected.', 'start': 1604.058, 'duration': 2.923}, {'end': 1607.922, 'text': 'This one.', 'start': 1607.521, 'duration': 0.401}, {'end': 1612.346, 'text': 'Zero distance and that is A.', 'start': 1608.823, 'duration': 3.523}, {'end': 1614.588, 'text': 'That is A.', 'start': 1612.346, 'duration': 2.242}, {'end': 1616.71, 'text': 'We have reached to the source vertex.', 'start': 1614.588, 'duration': 2.122}, {'end': 1617.611, 'text': 'That is zero.', 'start': 1616.73, 'duration': 0.881}, {'end': 1620.954, 'text': 'So the path from A to D is A.', 'start': 1618.932, 'duration': 2.022}], 'summary': 'Path from a to d is a with 0 distance.', 'duration': 31.838, 'max_score': 1514.423, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/smHnz2RHJBY/pics/smHnz2RHJBY1514423.jpg'}], 'start': 1014.952, 'title': "Dijkstra's algorithm and shortest path calculation", 'summary': "Provides a detailed explanation of dijkstra's algorithm for finding the shortest path in a graph, using specific examples and calculations. it also illustrates the selection of vertices, updating distances, and the application of the algorithm to find the shortest path, with a shortest distance of 9 and the specific path a to d via c and b.", 'chapters': [{'end': 1264.857, 'start': 1014.952, 'title': "Dijkstra's algorithm for shortest path", 'summary': "Provides a detailed explanation of dijkstra's algorithm for finding the shortest path in a graph, using specific examples and calculations to demonstrate the process.", 'duration': 249.905, 'highlights': ['The algorithm initializes the distances from the source vertex to all other vertices, setting the distance of the source vertex to itself as 0 and all other distances as infinity.', 'Selection of the vertex with the minimum distance vector, updating distances, and proceeding to calculate distances from the selected vertex to adjacent vertices forms the core of the algorithm.', 'The process involves updating the distances from the selected vertex to adjacent vertices based on the calculated costs, with the aim of finding the minimum distance path to each vertex.']}, {'end': 1402.398, 'start': 1266.775, 'title': 'Dijkstra algorithm explanation', 'summary': 'Explains the dijkstra algorithm with an example, demonstrating the selection of vertices, updating distances, and the application of the algorithm to find the shortest path in a graph.', 'duration': 135.623, 'highlights': ['The algorithm selects vertices with minimum distance, updating their distances and marking them as visited.', 'The algorithm iteratively selects vertices and updates their distances based on the edge costs, eventually finding the shortest path in the graph.', 'The process involves updating distances from the selected vertex to its adjacent vertices based on the edge costs and comparing with the existing distances.']}, {'end': 1620.954, 'start': 1402.398, 'title': 'Shortest path and distance calculation', 'summary': 'Provides a detailed explanation of finding the shortest distance and path from vertex a to d in a graph, with the shortest distance being 9 and the path being a to d via c and b.', 'duration': 218.556, 'highlights': ['The shortest distance from A to D is 9, with the path being A to D via C and B The chapter explains how to find the shortest distance and the path from vertex A to D in a graph, with the shortest distance being 9 and the path being A to D via C and B.', 'The process of finding the path involves moving backward through the vertices and updating the path based on the changes in distance values The process of finding the path involves moving backward through the vertices and updating the path based on the changes in distance values as demonstrated with the examples of changing distances for vertices B and C.', 'The method involves identifying the selected vertices and moving backward until reaching the source vertex with a distance of zero The method involves identifying the selected vertices and moving backward until reaching the source vertex with a distance of zero, as shown in the example where the path from A to D ends at vertex A with a distance of zero.']}], 'duration': 606.002, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/smHnz2RHJBY/pics/smHnz2RHJBY1014952.jpg', 'highlights': ['The algorithm selects vertices with minimum distance, updating their distances and marking them as visited.', 'The process involves updating distances from the selected vertex to its adjacent vertices based on the edge costs and comparing with the existing distances.', 'The method involves identifying the selected vertices and moving backward until reaching the source vertex with a distance of zero.']}, {'end': 2026.836, 'segs': [{'end': 1697.219, 'src': 'embed', 'start': 1661.617, 'weight': 0, 'content': [{'end': 1664.138, 'text': 'that is 9.', 'start': 1661.617, 'duration': 2.521}, {'end': 1667.358, 'text': 'same suppose the.', 'start': 1664.138, 'duration': 3.22}, {'end': 1675.6, 'text': 'you have to find out shortest path and shortest distance from a to e, from a to b.', 'start': 1667.358, 'duration': 8.242}, {'end': 1679.796, 'text': 'suppose, okay, what is the path?', 'start': 1675.6, 'duration': 4.196}, {'end': 1690.758, 'text': 'and what is the distance a to b, the shortest distance is you simply just check this table and you can quickly say that the shortest distance is 8,', 'start': 1679.796, 'duration': 10.962}, {'end': 1695.499, 'text': 'a to b, and find out in this column what is that selected.', 'start': 1690.758, 'duration': 4.741}, {'end': 1697.219, 'text': 'that number is 8.', 'start': 1695.499, 'duration': 1.72}], 'summary': 'The shortest distance from a to b is 8.', 'duration': 35.602, 'max_score': 1661.617, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/smHnz2RHJBY/pics/smHnz2RHJBY1661617.jpg'}, {'end': 1812.179, 'src': 'embed', 'start': 1784.152, 'weight': 1, 'content': [{'end': 1789.055, 'text': 'you can find out using that table the path as well as the shortest distance.', 'start': 1784.152, 'duration': 4.903}, {'end': 1793.738, 'text': 'Now the drawback of this diastro algorithm is what it will not work.', 'start': 1789.655, 'duration': 4.083}, {'end': 1796.96, 'text': "See, I'm not saying that it will not work.", 'start': 1794.558, 'duration': 2.402}, {'end': 1801.983, 'text': 'It may or may not work when the edge weight are negative.', 'start': 1797.12, 'duration': 4.863}, {'end': 1805.004, 'text': "I'll show you with the help of one example.", 'start': 1802.063, 'duration': 2.941}, {'end': 1809.378, 'text': 'Okay, okay, now let us take this graph.', 'start': 1805.545, 'duration': 3.833}, {'end': 1812.179, 'text': 'which one is having negative edge weight, that is minus 10.', 'start': 1809.378, 'duration': 2.801}], 'summary': 'Dijkstra algorithm finds shortest path, but may not work with negative edge weights.', 'duration': 28.027, 'max_score': 1784.152, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/smHnz2RHJBY/pics/smHnz2RHJBY1784152.jpg'}, {'end': 1958.335, 'src': 'embed', 'start': 1933.56, 'weight': 2, 'content': [{'end': 1941.524, 'text': 'so diastereo algorithm in this case is having the wrong shortest distance, because according to diastereo algorithm,', 'start': 1933.56, 'duration': 7.964}, {'end': 1944.366, 'text': 'the shortest distance from 1 to 2 is 5.', 'start': 1941.524, 'duration': 2.842}, {'end': 1945.747, 'text': 'but that is not actually true.', 'start': 1944.366, 'duration': 1.381}, {'end': 1953.412, 'text': 'the shortest distance from 1 to 2 is 1, through 1 to 3 to 4 to 2.', 'start': 1945.747, 'duration': 7.665}, {'end': 1956.394, 'text': 'so that is the main problem of diastereo algorithm.', 'start': 1953.412, 'duration': 2.982}, {'end': 1958.335, 'text': 'see, that is not always true.', 'start': 1956.394, 'duration': 1.941}], 'summary': 'The diastereo algorithm incorrectly calculates the shortest distance from 1 to 2 as 5, whereas it is actually 1 through 1 to 3 to 4 to 2, highlighting a flaw in the algorithm.', 'duration': 24.775, 'max_score': 1933.56, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/smHnz2RHJBY/pics/smHnz2RHJBY1933560.jpg'}], 'start': 1623.624, 'title': 'Shortest path and diastereo algorithm limitations', 'summary': 'Discusses finding the shortest path and distance between vertices in a graph using a table, with an example of finding the shortest path and distance from a to b as 8. it also highlights the drawbacks of the algorithm when dealing with negative edge weights. additionally, it explains the limitations of the diastereo algorithm in finding the shortest distance in a graph, emphasizing its failure to produce accurate results due to negative edge weights and cycles with negative weights.', 'chapters': [{'end': 1812.179, 'start': 1623.624, 'title': 'Finding shortest path and distance', 'summary': 'Discusses using a table to find the shortest path and distance between vertices in a graph, demonstrating the process with the example of finding the shortest path and distance from a to b as 8, and highlighting the drawback of the algorithm when dealing with negative edge weights.', 'duration': 188.555, 'highlights': ['The algorithm demonstrates finding the shortest path and distance between vertices using a table, exemplified by the process of finding the shortest path and distance from A to B as 8, showcasing the step-by-step approach to determine the path and distance.', 'The drawback of the algorithm is highlighted as it may not work when dealing with negative edge weights, illustrated with the example of a graph with a negative edge weight of -10.']}, {'end': 2026.836, 'start': 1812.179, 'title': 'Diastereo algorithm shortcomings', 'summary': 'Explains the limitations of the diastereo algorithm in finding the shortest distance in a graph, highlighting that it may fail to produce accurate results due to negative edge weights and cycles with negative weights.', 'duration': 214.657, 'highlights': ["Diastereo algorithm may or may not work with negative edge weights, leading to potentially incorrect results. The diastereo algorithm's limitation lies in its potential failure to produce accurate results when dealing with negative edge weights, as it may or may not provide the correct shortest distance.", 'The algorithm will surely not work when there is a cycle with negative weight, as it will consistently yield incorrect results. The diastereo algorithm is guaranteed to fail when faced with a cycle in a graph that has negative edge weights, consistently producing incorrect results.', "The shortest distance from 1 to 2 is not always accurately computed by the diastereo algorithm, as it may yield incorrect results in certain scenarios. The diastereo algorithm's shortcomings are exemplified by its inability to consistently provide the correct shortest distance, as demonstrated by the case where the true shortest distance from 1 to 2 is 1, not 5 as indicated by the algorithm."]}], 'duration': 403.212, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/smHnz2RHJBY/pics/smHnz2RHJBY1623624.jpg', 'highlights': ['The algorithm demonstrates finding the shortest path and distance between vertices using a table, exemplified by the process of finding the shortest path and distance from A to B as 8, showcasing the step-by-step approach to determine the path and distance.', 'The drawback of the algorithm is highlighted as it may not work when dealing with negative edge weights, illustrated with the example of a graph with a negative edge weight of -10.', "The diastereo algorithm's limitation lies in its potential failure to produce accurate results when dealing with negative edge weights, as it may or may not provide the correct shortest distance.", 'The algorithm will surely not work when there is a cycle with negative weight, as it will consistently yield incorrect results. The diastereo algorithm is guaranteed to fail when faced with a cycle in a graph that has negative edge weights, consistently producing incorrect results.', "The shortest distance from 1 to 2 is not always accurately computed by the diastereo algorithm, as it may yield incorrect results in certain scenarios. The diastereo algorithm's shortcomings are exemplified by its inability to consistently provide the correct shortest distance, as demonstrated by the case where the true shortest distance from 1 to 2 is 1, not 5 as indicated by the algorithm."]}], 'highlights': ['The algorithm involves iteratively updating the shortest distance from the source node to all other nodes based on the current minimum distance found, with the distances of the neighboring nodes being compared and updated accordingly.', "The process ensures that the shortest path from the source node to all other nodes in the graph is efficiently calculated, with the example demonstrating the comparison and updating of distances based on the algorithm's criteria.", 'The Dijkstra algorithm works on undirected and directed graphs. The chapter emphasizes that the Dijkstra algorithm is applicable to both undirected and directed graphs, highlighting its versatility and broad utility.', 'The shortest distance from 0 to 6 is 11. The algorithm determines the shortest distance from 0 to 6 as 11, showcasing the effectiveness of the Dijkstra algorithm.', "Nodes with the shortest distance are selected and their neighboring nodes' distances are updated if the new calculated distance is less than the current distance, until all nodes are visited and the shortest distances are determined.", 'The main formula for calculating the shortest distance is distance of u plus cost of u to v, which is used to update the distance of v if it is less than the current distance (e.g., 0 + 4 < ∞).', 'The algorithm selects a vertex and identifies the shortest distances to other vertices, with the shortest distance being 4.', 'The example demonstrates the application of the formula by updating the distances from vertex 0 to vertex 1 (from ∞ to 4) and from vertex 0 to vertex 4 (from ∞ to 8).', 'The process involves updating distances from the selected vertex to other vertices while ensuring that distances are only updated if the new distance is less than the existing one.', 'The concept of infinity is used to represent unknown or unvisited vertices, and the comparison of distances with infinity determines the updating of the shortest path distances.', 'The concept of not updating the distance to a vertex that has already been selected is emphasized.', 'The algorithm selects vertices with minimum distance, updating their distances and marking them as visited.', 'The process involves updating distances from the selected vertex to its adjacent vertices based on the edge costs and comparing with the existing distances.', 'The method involves identifying the selected vertices and moving backward until reaching the source vertex with a distance of zero.', 'The algorithm demonstrates finding the shortest path and distance between vertices using a table, exemplified by the process of finding the shortest path and distance from A to B as 8, showcasing the step-by-step approach to determine the path and distance.', 'The drawback of the algorithm is highlighted as it may not work when dealing with negative edge weights, illustrated with the example of a graph with a negative edge weight of -10.', "The diastereo algorithm's limitation lies in its potential failure to produce accurate results when dealing with negative edge weights, as it may or may not provide the correct shortest distance.", 'The algorithm will surely not work when there is a cycle with negative weight, as it will consistently yield incorrect results. The diastereo algorithm is guaranteed to fail when faced with a cycle in a graph that has negative edge weights, consistently producing incorrect results.', "The shortest distance from 1 to 2 is not always accurately computed by the diastereo algorithm, as it may yield incorrect results in certain scenarios. The diastereo algorithm's shortcomings are exemplified by its inability to consistently provide the correct shortest distance, as demonstrated by the case where the true shortest distance from 1 to 2 is 1, not 5 as indicated by the algorithm."]}