title
6.14 Bellman Ford Algorithm-Single Source Shortest Path | Dynamic Programming

description
Step by step instructions showing how to run the Bellman-Ford Algorithm on a Graph to find out the Shortest Distance of all the Vertices from a Single Source Vertex. Drawbacks of the Bellman-Ford algorithm as well as the Time Complexity of this algorithm. DSA Full Course: https: https://www.youtube.com/playlist?list=PLdo5W4Nhv31bbKJzrsKfMpo_grxuLl8LU ****************************************** See Complete 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/ #bellmanford #dynamicprogramming #datastructures #jennyslectures

detail
{'title': '6.14 Bellman Ford Algorithm-Single Source Shortest Path | Dynamic Programming', 'heatmap': [{'end': 358.555, 'start': 309.2, 'weight': 0.727}, {'end': 596.138, 'start': 577.004, 'weight': 0.727}, {'end': 666.275, 'start': 628.211, 'weight': 0.822}], 'summary': 'Explains the bellman ford algorithm, a single source shortest path algorithm for finding the shortest distance from a single source to all other vertices of a weighted graph, highlighting its differences from dijkstra algorithm, capability to handle negative weights, slower speed compared to dijkstra algorithm, and its time complexity of o(ve) or o(n^3) in the case of a complete graph, along with limitations in handling graphs with negative weight cycles.', 'chapters': [{'end': 87.95, 'segs': [{'end': 28.364, 'src': 'embed', 'start': 0.489, 'weight': 2, 'content': [{'end': 4.751, 'text': 'hey guys, in this video i am going to discuss with you bellman ford algorithm.', 'start': 0.489, 'duration': 4.262}, {'end': 7.933, 'text': 'it is what it is a single source shortest path algorithm.', 'start': 4.751, 'duration': 3.182}, {'end': 13.576, 'text': 'it means it helps us find this shortest distance from a single source.', 'start': 7.933, 'duration': 5.643}, {'end': 23.481, 'text': 'so you can say from a vertex to all the other vertices of a weighted graph okay, then you will say that we have one more algorithm for this.', 'start': 13.576, 'duration': 9.905}, {'end': 25.062, 'text': 'that is diastro algorithm.', 'start': 23.481, 'duration': 1.581}, {'end': 25.442, 'text': 'but how?', 'start': 25.062, 'duration': 0.38}, {'end': 28.364, 'text': 'this bellman ford algorithm is different from diastro algorithm.', 'start': 25.442, 'duration': 2.922}], 'summary': 'Discussion on bellman ford algorithm for single source shortest path in weighted graphs.', 'duration': 27.875, 'max_score': 0.489, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KudAWAMiQog/pics/KudAWAMiQog489.jpg'}, {'end': 87.95, 'src': 'embed', 'start': 44.837, 'weight': 0, 'content': [{'end': 53.684, 'text': 'but bellman ford algorithm confirms that your answer is correct, even if your weighted graph is having negative weights.', 'start': 44.837, 'duration': 8.847}, {'end': 62.268, 'text': "okay, and although bellman ford algorithm is slower than diastra algorithm, so in some cases it's better to use diastra algorithm.", 'start': 54.324, 'duration': 7.944}, {'end': 66.03, 'text': "some cases it's better better to use bellman ford algorithm.", 'start': 62.268, 'duration': 3.762}, {'end': 71.193, 'text': "okay, then, in this video i'll discuss the working principle of this bellman ford algorithm,", 'start': 66.03, 'duration': 5.163}, {'end': 77.036, 'text': 'as well as the drawback of this algorithm and the time complexity of bellman ford algorithm.', 'start': 71.193, 'duration': 5.843}, {'end': 80.058, 'text': 'so let us start the simple funda.', 'start': 77.036, 'duration': 3.022}, {'end': 81.419, 'text': 'we will take this example.', 'start': 80.058, 'duration': 1.361}, {'end': 87.95, 'text': 'See, you can see that this is a weighted graph and directed graph having negative edge weights.', 'start': 82.426, 'duration': 5.524}], 'summary': 'Bellman ford algorithm handles negative weights, slower than dijkstra but useful in some cases.', 'duration': 43.113, 'max_score': 44.837, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KudAWAMiQog/pics/KudAWAMiQog44837.jpg'}], 'start': 0.489, 'title': 'Bellman ford algorithm', 'summary': 'Explains the bellman ford algorithm, a single source shortest path algorithm for finding the shortest distance from a single source to all other vertices of a weighted graph. it discusses its uniqueness from dijkstra algorithm, capability to handle negative weights, slower speed compared to dijkstra algorithm, and the working principle, drawback, and time complexity.', 'chapters': [{'end': 87.95, 'start': 0.489, 'title': 'Bellman ford algorithm', 'summary': 'Explains the bellman ford algorithm, a single source shortest path algorithm for finding the shortest distance from a single source to all other vertices of a weighted graph, including its uniqueness from dijkstra algorithm, capability to handle negative weights, slower speed compared to dijkstra algorithm, and the working principle, drawback, and time complexity.', 'duration': 87.461, 'highlights': ['Bellman Ford algorithm is unique as it can handle negative weights in a weighted graph, ensuring correct answers. Bellman Ford algorithm can handle negative weights, providing correct answers, unlike Dijkstra algorithm.', 'The algorithm is slower than Dijkstra algorithm, making Dijkstra algorithm preferable in some cases. Bellman Ford algorithm is slower than Dijkstra algorithm, leading to Dijkstra algorithm being preferred in certain scenarios.', 'The chapter discusses the working principle, drawback, and time complexity of the Bellman Ford algorithm. The chapter covers the working principle, drawback, and time complexity of the Bellman Ford algorithm.', 'Bellman Ford algorithm is a single source shortest path algorithm for finding the shortest distance from a single source to all other vertices of a weighted graph. Bellman Ford algorithm serves as a single source shortest path algorithm for determining the shortest distance from a single source to all other vertices in a weighted graph.']}], 'duration': 87.461, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KudAWAMiQog/pics/KudAWAMiQog489.jpg', 'highlights': ['Bellman Ford algorithm is unique as it can handle negative weights in a weighted graph, ensuring correct answers.', 'The algorithm is slower than Dijkstra algorithm, making Dijkstra algorithm preferable in some cases.', 'Bellman Ford algorithm is a single source shortest path algorithm for finding the shortest distance from a single source to all other vertices of a weighted graph.', 'The chapter discusses the working principle, drawback, and time complexity of the Bellman Ford algorithm.']}, {'end': 528.25, 'segs': [{'end': 147.08, 'src': 'embed', 'start': 88.571, 'weight': 0, 'content': [{'end': 95.836, 'text': 'The simple funda of this algorithm is what? You will go on relaxing all the edges.', 'start': 88.571, 'duration': 7.265}, {'end': 101.08, 'text': 'How many times? n minus 1 times.', 'start': 97.718, 'duration': 3.362}, {'end': 102.061, 'text': 'This one.', 'start': 101.741, 'duration': 0.32}, {'end': 107.666, 'text': 'this is the simple rule of this algorithm.', 'start': 103.464, 'duration': 4.202}, {'end': 110.308, 'text': 'go on relaxing all the edges.', 'start': 107.666, 'duration': 2.642}, {'end': 113.209, 'text': 'in this graph, n minus one times.', 'start': 110.308, 'duration': 2.901}, {'end': 117.652, 'text': 'and here n is what number of vertices in that graph?', 'start': 113.209, 'duration': 4.443}, {'end': 121.354, 'text': 'okay, so in this graph, number of vertices are one, two, three, four, five, six.', 'start': 117.652, 'duration': 3.702}, {'end': 125.191, 'text': 'Then we will relax all the edges.', 'start': 122.69, 'duration': 2.501}, {'end': 125.911, 'text': 'how many times??', 'start': 125.191, 'duration': 0.72}, {'end': 126.952, 'text': '5 times.', 'start': 125.931, 'duration': 1.021}, {'end': 129.072, 'text': '6 minus 1 that is 5 times.', 'start': 126.972, 'duration': 2.1}, {'end': 131.914, 'text': 'And then you will get the correct answer.', 'start': 129.773, 'duration': 2.141}, {'end': 138.056, 'text': 'If you will iterate the loop one more time that is 6th time then there would be no change.', 'start': 132.554, 'duration': 5.502}, {'end': 144.179, 'text': 'in the, you can say in the distance of any vertex.', 'start': 139.056, 'duration': 5.123}, {'end': 147.08, 'text': 'okay, now, what this relaxing means?', 'start': 144.179, 'duration': 2.901}], 'summary': 'Algorithm relaxes edges n-1 times to find correct distances in a graph with 6 vertices.', 'duration': 58.509, 'max_score': 88.571, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KudAWAMiQog/pics/KudAWAMiQog88571.jpg'}, {'end': 213.406, 'src': 'embed', 'start': 171.612, 'weight': 3, 'content': [{'end': 182.474, 'text': 'if distance of u plus cost of u and v is less than distance of v,', 'start': 171.612, 'duration': 10.862}, {'end': 194.676, 'text': 'then distance of v would be modified and it will become distance of u plus cost of u and v.', 'start': 182.474, 'duration': 12.202}, {'end': 197.277, 'text': 'this is what the relaxing means.', 'start': 194.676, 'duration': 2.601}, {'end': 205.28, 'text': 'so the very first step is what you write down all the edges.', 'start': 199.096, 'duration': 6.184}, {'end': 207.902, 'text': 'okay, suppose the single source is the.', 'start': 205.28, 'duration': 2.622}, {'end': 209.743, 'text': 'it is the single source shortest path problem.', 'start': 207.902, 'duration': 1.841}, {'end': 213.406, 'text': 'so suppose i am taking the source a here.', 'start': 209.743, 'duration': 3.663}], 'summary': "Relaxing edges to find shortest path for single source, starting with source 'a'.", 'duration': 41.794, 'max_score': 171.612, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KudAWAMiQog/pics/KudAWAMiQog171612.jpg'}, {'end': 270.768, 'src': 'embed', 'start': 242.053, 'weight': 1, 'content': [{'end': 246.898, 'text': 'Source is A and you have to find out the shortest distance from A to all other vertices.', 'start': 242.053, 'duration': 4.845}, {'end': 249.02, 'text': 'So distance of A to A is what? 0.', 'start': 246.938, 'duration': 2.082}, {'end': 255.466, 'text': 'And at first the distance of every other vertex would be what? Infinity.', 'start': 249.02, 'duration': 6.446}, {'end': 261.101, 'text': 'fine, now let us start the iteration.', 'start': 257.738, 'duration': 3.363}, {'end': 262.862, 'text': 'how many iterations would be there?', 'start': 261.101, 'duration': 1.761}, {'end': 264.023, 'text': 'n minus 1.', 'start': 262.862, 'duration': 1.161}, {'end': 270.768, 'text': 'see, go on relaxing all there is n minus 1 times, that is, if we have 6 vertices, then 5 iterations would be there.', 'start': 264.023, 'duration': 6.745}], 'summary': 'Find shortest distance from a to all other vertices using n-1 iterations.', 'duration': 28.715, 'max_score': 242.053, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KudAWAMiQog/pics/KudAWAMiQog242053.jpg'}, {'end': 358.555, 'src': 'heatmap', 'start': 309.2, 'weight': 0.727, 'content': [{'end': 311.943, 'text': '6. then here what you will write.', 'start': 309.2, 'duration': 2.743}, {'end': 314.765, 'text': 'you will update the distance 6.', 'start': 311.943, 'duration': 2.822}, {'end': 317.168, 'text': 'this is how we will use this formula.', 'start': 314.765, 'duration': 2.403}, {'end': 321.111, 'text': 'next edge is what ac, ac 0 plus 4.', 'start': 317.168, 'duration': 3.943}, {'end': 322.793, 'text': 'yes, this is less than infinity.', 'start': 321.111, 'duration': 1.682}, {'end': 324.474, 'text': 'then updated ad.', 'start': 322.793, 'duration': 1.681}, {'end': 325.535, 'text': 'ad 0 plus 5.', 'start': 324.474, 'duration': 1.061}, {'end': 329.862, 'text': 'yes, you will update it 5, b, e.', 'start': 325.535, 'duration': 4.327}, {'end': 330.683, 'text': 'check it out.', 'start': 329.862, 'duration': 0.821}, {'end': 332.085, 'text': 'b, e.', 'start': 330.683, 'duration': 1.402}, {'end': 334.088, 'text': 'distance of b is what six.', 'start': 332.085, 'duration': 2.003}, {'end': 335.87, 'text': 'six minus one, that is five.', 'start': 334.088, 'duration': 1.782}, {'end': 338.534, 'text': 'we will update this one because five is less than this one.', 'start': 335.87, 'duration': 2.664}, {'end': 343.759, 'text': 'then ce, ce, distance of c is 4.', 'start': 339.335, 'duration': 4.424}, {'end': 346.503, 'text': '4 plus 3 is what 7, but 5 is better.', 'start': 343.759, 'duration': 2.744}, {'end': 348.885, 'text': "don't update dc.", 'start': 346.503, 'duration': 2.382}, {'end': 351.548, 'text': 'dc distance of d is 5, 5 minus 2.', 'start': 348.885, 'duration': 2.663}, {'end': 352.449, 'text': 'that is 3.', 'start': 351.548, 'duration': 0.901}, {'end': 353.51, 'text': 'yes, 3 is better.', 'start': 352.449, 'duration': 1.061}, {'end': 355.232, 'text': 'then we will update it.', 'start': 353.51, 'duration': 1.722}, {'end': 357.755, 'text': 'df 5 minus 1.', 'start': 355.232, 'duration': 2.523}, {'end': 358.555, 'text': 'that is 4.', 'start': 357.755, 'duration': 0.8}], 'summary': 'Updating distances using formula, with specific values.', 'duration': 49.355, 'max_score': 309.2, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KudAWAMiQog/pics/KudAWAMiQog309200.jpg'}], 'start': 88.571, 'title': "Graph algorithm fundamentals and dijkstra's algorithm", 'summary': "Covers the fundamental concept of graph algorithms, emphasizing relaxing edges n minus 1 times, and its application in a graph with six vertices. it also explains dijkstra's algorithm for finding the shortest path in a graph, with a detailed example resulting in the shortest distances of a: 0, b: 1, c: 3, d: 5, e: 0, f: 3.", 'chapters': [{'end': 147.08, 'start': 88.571, 'title': 'Graph algorithm fundamentals', 'summary': 'Explains the fundamental concept of a graph algorithm, emphasizing the rule of relaxing edges n minus 1 times and its application in a graph with six vertices.', 'duration': 58.509, 'highlights': ['The simple rule of the graph algorithm is to relax all edges n minus 1 times, where n represents the number of vertices in the graph, which in this case is demonstrated for a graph with six vertices.', 'Iterating the loop five times (6 minus 1) will result in the correct answer in the context of relaxing edges in the graph algorithm.', 'Relaxing edges means adjusting the distance of vertices, and it is emphasized to be performed n minus 1 times in the graph algorithm.']}, {'end': 528.25, 'start': 147.08, 'title': "Dijkstra's algorithm explained", 'summary': "Explains dijkstra's algorithm for finding the shortest path in a graph, with a detailed example of updating distances for each iteration, resulting in the shortest distances of a: 0, b: 1, c: 3, d: 5, e: 0, f: 3.", 'duration': 381.17, 'highlights': ['The algorithm iterates n-1 times, where n is the number of vertices, to find the shortest distances.', 'The algorithm updates distances by comparing the sum of the distance of the source vertex and the cost of the edge with the current distance of the target vertex.', 'In the detailed example, the algorithm computes the shortest distances from the source vertex A to all other vertices, resulting in distances of A: 0, B: 1, C: 3, D: 5, E: 0, F: 3.']}], 'duration': 439.679, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KudAWAMiQog/pics/KudAWAMiQog88571.jpg', 'highlights': ['The simple rule of the graph algorithm is to relax all edges n minus 1 times, where n represents the number of vertices in the graph, which in this case is demonstrated for a graph with six vertices.', 'The algorithm iterates n-1 times, where n is the number of vertices, to find the shortest distances.', 'Iterating the loop five times (6 minus 1) will result in the correct answer in the context of relaxing edges in the graph algorithm.', 'The algorithm updates distances by comparing the sum of the distance of the source vertex and the cost of the edge with the current distance of the target vertex.', 'Relaxing edges means adjusting the distance of vertices, and it is emphasized to be performed n minus 1 times in the graph algorithm.', 'In the detailed example, the algorithm computes the shortest distances from the source vertex A to all other vertices, resulting in distances of A: 0, B: 1, C: 3, D: 5, E: 0, F: 3.']}, {'end': 942.254, 'segs': [{'end': 599.841, 'src': 'heatmap', 'start': 577.004, 'weight': 0.727, 'content': [{'end': 587.486, 'text': 'then you can say this is order of n square and in case of complete graph, see in complete graph how many edges would be there.', 'start': 577.004, 'duration': 10.482}, {'end': 596.138, 'text': 'the formula is what the number of edges would be there in complete graph v into v, minus 1, divide by 2.', 'start': 587.486, 'duration': 8.652}, {'end': 599.841, 'text': 'or you can say n into n, minus 1, divided by 2.', 'start': 596.138, 'duration': 3.703}], 'summary': 'Order of n square, complete graph has v(v-1)/2 edges.', 'duration': 22.837, 'max_score': 577.004, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KudAWAMiQog/pics/KudAWAMiQog577004.jpg'}, {'end': 671.618, 'src': 'heatmap', 'start': 628.211, 'weight': 0, 'content': [{'end': 632.113, 'text': 'So this is the time complexity in the case of complete graph.', 'start': 628.211, 'duration': 3.902}, {'end': 638.637, 'text': 'When you apply Bellman Ford algorithm or simply you can say this one is order of n cube.', 'start': 632.133, 'duration': 6.504}, {'end': 643.316, 'text': 'fine. now we will check the drawback of this algorithm.', 'start': 640.333, 'duration': 2.983}, {'end': 644.457, 'text': 'let us take this example.', 'start': 643.316, 'duration': 1.141}, {'end': 656.048, 'text': 'we are having this graph having negative weights and belmont ford algorithm drawback is that belmont ford algorithm will not work if the graph contains any negative weight cycle.', 'start': 644.457, 'duration': 11.591}, {'end': 666.275, 'text': 'negative weight cycle means what if a graph contains any cycle whose edge sum is negative?', 'start': 656.949, 'duration': 9.326}, {'end': 667.275, 'text': 'here we have one cycle.', 'start': 666.275, 'duration': 1}, {'end': 671.618, 'text': 'this one is this, this and this this one is a cycle.', 'start': 667.275, 'duration': 4.343}], 'summary': 'Bellman ford algorithm on complete graph is o(n^3), but may fail with negative weight cycles.', 'duration': 46.229, 'max_score': 628.211, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KudAWAMiQog/pics/KudAWAMiQog628211.jpg'}, {'end': 860.371, 'src': 'embed', 'start': 827.405, 'weight': 2, 'content': [{'end': 828.526, 'text': 'Number of vertices is minus 1.', 'start': 827.405, 'duration': 1.121}, {'end': 831.71, 'text': 'Okay Now according to Bellman-Ford algorithm.', 'start': 828.526, 'duration': 3.184}, {'end': 832.21, 'text': 'We are done.', 'start': 831.73, 'duration': 0.48}, {'end': 834.132, 'text': 'And we have find out.', 'start': 832.791, 'duration': 1.341}, {'end': 839.786, 'text': 'the shortest path of all the vertices from the given vertex.', 'start': 835.205, 'duration': 4.581}, {'end': 841.887, 'text': "but let's check it out.", 'start': 839.786, 'duration': 2.101}, {'end': 850.849, 'text': 'if you will do one more iterations, then what will happen in the fourth iteration?', 'start': 841.887, 'duration': 8.962}, {'end': 860.371, 'text': "according to bellman ford algorithm in the fourth, in the fourth iteration there should not be any change in the distances because it's already over.", 'start': 850.849, 'duration': 9.522}], 'summary': 'Bellman-ford algorithm finds shortest path for vertices from given vertex.', 'duration': 32.966, 'max_score': 827.405, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KudAWAMiQog/pics/KudAWAMiQog827405.jpg'}, {'end': 928.609, 'src': 'embed', 'start': 900.934, 'weight': 3, 'content': [{'end': 905.918, 'text': 'Or you can say 7 minus 6, that is 1, and 1 is less than 2.', 'start': 900.934, 'duration': 4.984}, {'end': 908.38, 'text': 'then distance would be updated.', 'start': 905.918, 'duration': 2.462}, {'end': 913.865, 'text': 'But that is not the case in the Bellman Ford algorithm.', 'start': 909.561, 'duration': 4.304}, {'end': 918.95, 'text': 'So you can say this graph contains a negative weight cycle.', 'start': 913.905, 'duration': 5.045}, {'end': 924.447, 'text': 'So this is the drawback of Bellman-Ford algorithm.', 'start': 921.766, 'duration': 2.681}, {'end': 927.908, 'text': 'This algorithm will not work if the graph contains negative weight cycle.', 'start': 924.487, 'duration': 3.421}, {'end': 928.609, 'text': 'See cycle.', 'start': 927.968, 'duration': 0.641}], 'summary': 'Bellman-ford algorithm fails with negative weight cycles.', 'duration': 27.675, 'max_score': 900.934, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KudAWAMiQog/pics/KudAWAMiQog900934.jpg'}], 'start': 528.25, 'title': 'Bellman-ford algorithm', 'summary': 'Discusses the bellman-ford algorithm, highlighting its time complexity of o(ve) or o(n^3) in the case of a complete graph and its limitation in handling graphs with negative weight cycles, and presents 3 iterations demonstrating the shortest path of all vertices from a given vertex along with the condition for the algorithm not providing the correct answer in the presence of a negative weight cycle.', 'chapters': [{'end': 731.889, 'start': 528.25, 'title': 'Bellman-ford algorithm time complexity', 'summary': 'Explains the time complexity of the bellman-ford algorithm, which is o(ve) or o(n^3) in the case of a complete graph, and highlights its drawback of not working with graphs containing negative weight cycles.', 'duration': 203.639, 'highlights': ['The time complexity of the Bellman-Ford algorithm is O(VE) or O(n^3) in the case of a complete graph, where V represents the number of vertices and E represents the number of edges.', 'The algorithm will not work if the graph contains any negative weight cycle, as it will not give the correct answer in such cases.']}, {'end': 942.254, 'start': 731.889, 'title': 'Bellman-ford algorithm', 'summary': 'Discusses the bellman-ford algorithm with 3 iterations showing the shortest path of all vertices from the given vertex and the condition for the algorithm not giving a correct answer due to the presence of a negative weight cycle in the graph.', 'duration': 210.365, 'highlights': ['The Bellman-Ford algorithm is demonstrated with 3 iterations to find the shortest path of all vertices from the given vertex.', 'The chapter explains the condition for the Bellman-Ford algorithm not giving a correct answer, indicating the presence of a negative weight cycle in the graph.', "The algorithm's limitation is highlighted, stating that it will not work if the graph contains a negative weight cycle, but will work fine if the graph contains negative weight edge only."]}], 'duration': 414.004, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/KudAWAMiQog/pics/KudAWAMiQog528250.jpg', 'highlights': ['The time complexity of the Bellman-Ford algorithm is O(VE) or O(n^3) in the case of a complete graph, where V represents the number of vertices and E represents the number of edges.', 'The algorithm will not work if the graph contains any negative weight cycle, as it will not give the correct answer in such cases.', 'The Bellman-Ford algorithm is demonstrated with 3 iterations to find the shortest path of all vertices from the given vertex.', 'The chapter explains the condition for the Bellman-Ford algorithm not giving a correct answer, indicating the presence of a negative weight cycle in the graph.', "The algorithm's limitation is highlighted, stating that it will not work if the graph contains a negative weight cycle, but will work fine if the graph contains negative weight edge only."]}], 'highlights': ['Bellman Ford algorithm is unique as it can handle negative weights in a weighted graph, ensuring correct answers.', 'The algorithm is slower than Dijkstra algorithm, making Dijkstra algorithm preferable in some cases.', 'The time complexity of the Bellman-Ford algorithm is O(VE) or O(n^3) in the case of a complete graph, where V represents the number of vertices and E represents the number of edges.', 'The simple rule of the graph algorithm is to relax all edges n minus 1 times, where n represents the number of vertices in the graph, which in this case is demonstrated for a graph with six vertices.', 'The algorithm iterates n-1 times, where n is the number of vertices, to find the shortest distances.', 'The algorithm updates distances by comparing the sum of the distance of the source vertex and the cost of the edge with the current distance of the target vertex.', 'The chapter discusses the working principle, drawback, and time complexity of the Bellman Ford algorithm.', 'The algorithm will not work if the graph contains any negative weight cycle, as it will not give the correct answer in such cases.', 'The Bellman-Ford algorithm is demonstrated with 3 iterations to find the shortest path of all vertices from the given vertex.', 'The chapter explains the condition for the Bellman-Ford algorithm not giving a correct answer, indicating the presence of a negative weight cycle in the graph.']}