title

G-42. Floyd Warshall Algorithm

description

GfG-Problem Link: https://bit.ly/3JZlk4a
C++/Java/Codes and Notes Link: https://takeuforward.org/data-structure/floyd-warshall-algorithm-g-42/
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-42. Floyd Warshall Algorithm', 'heatmap': [{'end': 370.766, 'start': 304.916, 'weight': 0.928}, {'end': 779.971, 'start': 653.482, 'weight': 0.803}, {'end': 1469.636, 'start': 1358.577, 'weight': 0.971}, {'end': 1778.087, 'start': 1737.128, 'weight': 0.79}], 'summary': "Covers floyd's virtual shortest path algorithm for detecting negative cycles and identifying the shortest path, converting undirected graphs for applying floyd's algorithm, computing route values, evaluating shortest paths, and finding the shortest distance between every pair of vertices in an edge-weighted directed graph.", 'chapters': [{'end': 579.199, 'segs': [{'end': 98.954, 'src': 'embed', 'start': 71.676, 'weight': 1, 'content': [{'end': 80.309, 'text': 'remember this it helps you detect negative cycles as well, helps you detect negative cycles as well.', 'start': 71.676, 'duration': 8.633}, {'end': 85.487, 'text': "So I hope pretty much you've understood what you need to find.", 'start': 81.345, 'duration': 4.142}, {'end': 87.708, 'text': 'Now what is the shortest path? Very simple.', 'start': 85.527, 'duration': 2.181}, {'end': 95.292, 'text': "If I'm asking you from 0 to 1 and I ask you what is the shortest path in order to reach from 0 to 1.", 'start': 88.049, 'duration': 7.243}, {'end': 97.153, 'text': 'So you can take multiple paths.', 'start': 95.292, 'duration': 1.861}, {'end': 98.954, 'text': 'One of the paths will take you 6.', 'start': 97.233, 'duration': 1.721}], 'summary': 'Detect negative cycles, find shortest path from 0 to 1, with one path taking 6.', 'duration': 27.278, 'max_score': 71.676, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YbY8cVwWAvw/pics/YbY8cVwWAvw71676.jpg'}, {'end': 153.509, 'src': 'embed', 'start': 124.87, 'weight': 0, 'content': [{'end': 127.072, 'text': "This is the shortest path, if I'm asking you.", 'start': 124.87, 'duration': 2.202}, {'end': 128.532, 'text': "That's the definition of shortest path.", 'start': 127.112, 'duration': 1.42}, {'end': 134.297, 'text': 'Any path that takes the least amount of edge weights is known as the shortest path.', 'start': 129.013, 'duration': 5.284}, {'end': 135.858, 'text': 'So what is the.', 'start': 134.657, 'duration': 1.201}, {'end': 140.219, 'text': 'thought process behind the blurred virtual algorithm.', 'start': 136.977, 'duration': 3.242}, {'end': 141.721, 'text': "now it's very simple.", 'start': 140.219, 'duration': 1.502}, {'end': 152.128, 'text': 'it states go via every edge, go via every node, rather or go via every vertex or node, whatever you wish to write.', 'start': 141.721, 'duration': 10.407}, {'end': 153.509, 'text': "so it's very simple.", 'start': 152.128, 'duration': 1.381}], 'summary': 'Shortest path is defined by least edge weights. blurred virtual algorithm involves going via every edge and node.', 'duration': 28.639, 'max_score': 124.87, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YbY8cVwWAvw/pics/YbY8cVwWAvw124870.jpg'}, {'end': 370.766, 'src': 'heatmap', 'start': 304.916, 'weight': 0.928, 'content': [{'end': 308.499, 'text': 'And can I say this is nothing but I go from straight i to j.', 'start': 304.916, 'duration': 3.583}, {'end': 311.436, 'text': 'which is nothing but the edge itself.', 'start': 309.875, 'duration': 1.561}, {'end': 318.178, 'text': 'And can I say this, this, this to be K, assume.', 'start': 312.136, 'duration': 6.042}, {'end': 322.46, 'text': 'So can I write the path to be minimum of?', 'start': 318.579, 'duration': 3.881}, {'end': 332.384, 'text': 'if you try out all the Ks, it will be from I to K, very obvious, because you go from 0 to 2 and then from 2 to this,', 'start': 322.46, 'duration': 9.924}, {'end': 334.745, 'text': 'which is nothing but the J correct?', 'start': 332.384, 'duration': 2.361}, {'end': 338.527, 'text': 'So can I write this plus J of K?', 'start': 334.985, 'duration': 3.542}, {'end': 341.094, 'text': 'i can.', 'start': 339.713, 'duration': 1.381}, {'end': 342.314, 'text': "that's what the path is.", 'start': 341.094, 'duration': 1.22}, {'end': 346.496, 'text': "from i to k i'll go and from g to k is what i have to go.", 'start': 342.314, 'duration': 4.182}, {'end': 354.28, 'text': 'and if i take minimum of all of them five, five, four, minimum of all of the go through vertex, then the answer.', 'start': 346.496, 'duration': 7.784}, {'end': 356.161, 'text': "i'll have the answer somewhere down the line.", 'start': 354.28, 'duration': 1.881}, {'end': 360.283, 'text': "i've understood, but i need to implement this on a wider scale.", 'start': 356.161, 'duration': 4.122}, {'end': 361.984, 'text': 'what do i mean by a wider scale?', 'start': 360.283, 'duration': 1.701}, {'end': 370.766, 'text': 'because over here, zero to four was not a direct edge, because zero to four meant it went via two, so it was going via two.', 'start': 361.984, 'duration': 8.782}], 'summary': 'Finding the minimum path from i to j via k using vertex values.', 'duration': 65.85, 'max_score': 304.916, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YbY8cVwWAvw/pics/YbY8cVwWAvw304916.jpg'}, {'end': 465.253, 'src': 'embed', 'start': 437.234, 'weight': 2, 'content': [{'end': 442.579, 'text': 'till now, in all the problems, we have been using the adjacency list in order to store the graph.', 'start': 437.234, 'duration': 5.345}, {'end': 446.922, 'text': "but in the lecture 2, i've also taught you one more method, which is the adjacency matrix method.", 'start': 442.579, 'duration': 4.343}, {'end': 452.328, 'text': "So you're going to use the adjacency matrix method in order to store this particular graph.", 'start': 447.583, 'duration': 4.745}, {'end': 453.529, 'text': "Okay, it's very simple.", 'start': 452.649, 'duration': 0.88}, {'end': 456.473, 'text': "In case you haven't seen the lecture 2, it's very, very simple.", 'start': 453.89, 'duration': 2.583}, {'end': 465.253, 'text': 'Something we know for sure is if 0 is the node and I want to go to 0 itself, the cost will be 0.', 'start': 456.953, 'duration': 8.3}], 'summary': 'Lecture 2 introduces adjacency matrix method for graph storage.', 'duration': 28.019, 'max_score': 437.234, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YbY8cVwWAvw/pics/YbY8cVwWAvw437234.jpg'}], 'start': 3.263, 'title': "Floyd's virtual shortest path", 'summary': "Presents the floyd's virtual shortest path algorithm, a multi-source shortest path algorithm for detecting negative cycles and identifying the shortest path between any two nodes in a graph, along with a demonstration of implementing the algorithm using an adjacency matrix.", 'chapters': [{'end': 579.199, 'start': 3.263, 'title': "Floyd's virtual shortest path", 'summary': "Presents the floyd's virtual shortest path algorithm, a multi-source shortest path algorithm that helps detect negative cycles and identifies the shortest path between any two nodes in a graph, with a demonstration of implementing the algorithm using an adjacency matrix.", 'duration': 575.936, 'highlights': ["Floyd's Virtual Shortest Path algorithm is a multi-source shortest path algorithm that identifies the shortest path between any two nodes in a graph. It allows finding the shortest path between any two nodes in a graph, making it a multi-source algorithm.", 'The algorithm helps detect negative cycles in a graph. It aids in identifying negative cycles within the graph, providing a solution for graphs containing negative cycles.', 'The implementation demonstration uses an adjacency matrix method to store the graph. The demonstration illustrates the use of an adjacency matrix method to store the graph, providing a step-by-step guide on implementing the algorithm.']}], 'duration': 575.936, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YbY8cVwWAvw/pics/YbY8cVwWAvw3263.jpg', 'highlights': ["Floyd's Virtual Shortest Path algorithm is a multi-source shortest path algorithm that identifies the shortest path between any two nodes in a graph. It allows finding the shortest path between any two nodes in a graph, making it a multi-source algorithm.", 'The algorithm helps detect negative cycles in a graph. It aids in identifying negative cycles within the graph, providing a solution for graphs containing negative cycles.', 'The implementation demonstration uses an adjacency matrix method to store the graph. The demonstration illustrates the use of an adjacency matrix method to store the graph, providing a step-by-step guide on implementing the algorithm.']}, {'end': 958.494, 'segs': [{'end': 604.718, 'src': 'embed', 'start': 579.199, 'weight': 1, 'content': [{'end': 587.825, 'text': "so what i've done is i've assigned the cost make sure everyone else is infinity which means unreachable as of now.", 'start': 579.199, 'duration': 8.626}, {'end': 590.687, 'text': 'which means unreachable as of now.', 'start': 587.825, 'duration': 2.862}, {'end': 596.392, 'text': 'so this is the initial cost matrix which you can always derive from the given graph.', 'start': 590.687, 'duration': 5.705}, {'end': 601.396, 'text': 'now you must be thinking, but striver, this is a dg, a directed graph.', 'start': 596.392, 'duration': 5.004}, {'end': 602.757, 'text': "what if it's a ug?", 'start': 601.396, 'duration': 1.361}, {'end': 604.718, 'text': 'how will we implement the floyd motion?', 'start': 602.757, 'duration': 1.961}], 'summary': 'Initial cost matrix derived from directed graph for floyd motion implementation.', 'duration': 25.519, 'max_score': 579.199, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YbY8cVwWAvw/pics/YbY8cVwWAvw579199.jpg'}, {'end': 779.971, 'src': 'heatmap', 'start': 626.227, 'weight': 0, 'content': [{'end': 636.717, 'text': 'okay. so if you have to apply fluid motion in an undirected graph, just split that edge into two edges of same weights.', 'start': 626.227, 'duration': 10.49}, {'end': 641.722, 'text': "that's how you can easily convert a ug to a directed graph.", 'start': 636.717, 'duration': 5.005}, {'end': 643.683, 'text': 'so this is the initial cost.', 'start': 641.722, 'duration': 1.961}, {'end': 644.905, 'text': 'now, what did i say?', 'start': 643.683, 'duration': 1.222}, {'end': 652.532, 'text': "let's, as of now, assume that i'm going to move via vertex zero.", 'start': 644.905, 'duration': 7.627}, {'end': 654.203, 'text': "That's my first thing.", 'start': 653.482, 'duration': 0.721}, {'end': 656.826, 'text': "I'll move via vertex 0.", 'start': 654.663, 'duration': 2.163}, {'end': 661.971, 'text': 'So if I move via vertex 0, I will have some upgraded distance, something for sure.', 'start': 656.826, 'duration': 5.145}, {'end': 667.918, 'text': "So let's start off with vertex 0 and see what will be the resultant matrix that we will get.", 'start': 662.232, 'duration': 5.686}, {'end': 671.822, 'text': "Now what I'm saying, you have to move via the root 0.", 'start': 668.419, 'duration': 3.403}, {'end': 680.067, 'text': 'So can I say at first this is 0 to 0, stored as 0, next is 0 to 1.', 'start': 671.822, 'duration': 8.245}, {'end': 687.31, 'text': "so which means you're moving via root 0, which is 0 to 0, plus 0 to 1.", 'start': 680.067, 'duration': 7.243}, {'end': 694.553, 'text': "can i say it's similar to saying 0 to 1, because 0 to 0 will always be 0, and 0 to 1 is what we have already stored 2..", 'start': 687.31, 'duration': 7.243}, {'end': 697.034, 'text': 'so you can just copy paste 2.', 'start': 694.553, 'duration': 2.481}, {'end': 705.697, 'text': "next is 0 to 2 Can I say it's similar? 0 to 2 is nothing but saying 0 to via 0 by the way.", 'start': 697.034, 'duration': 8.663}, {'end': 711.559, 'text': 'Via 0 means 0 to 0 which is again 0 plus 0 to 2 which is nothing but infinity.', 'start': 706.057, 'duration': 5.502}, {'end': 715.62, 'text': 'So similarly this will also be infinity y.', 'start': 712.199, 'duration': 3.421}, {'end': 720.141, 'text': '0 to 3 will mean 0 to 0 and 0 to 3.', 'start': 715.64, 'duration': 4.501}, {'end': 722.062, 'text': 'Similarly this will mean 1 to 0.', 'start': 720.141, 'duration': 1.921}, {'end': 730.694, 'text': 'What does 1 to 0 mean? 1 to 0 means via 0 means 1 to 0 itself and then 0 to 0.', 'start': 722.062, 'duration': 8.632}, {'end': 736.919, 'text': "Via 0 means that only, right? Via 0 means that because this is i, this is j, you're moving via 0.", 'start': 730.694, 'duration': 6.225}, {'end': 743.804, 'text': 'So can I say this one, this one, this one will just copy paste these values? Just go across, copy paste these values.', 'start': 736.919, 'duration': 6.885}, {'end': 749.228, 'text': "Why? Because very simple, if your destination is 0, you can't move via 0.", 'start': 743.884, 'duration': 5.344}, {'end': 752.331, 'text': "So whatever you're taking in order to reach 0, that is what you copy paste.", 'start': 749.228, 'duration': 3.103}, {'end': 754.873, 'text': "What about these places? Let's fill them up.", 'start': 752.711, 'duration': 2.162}, {'end': 757.675, 'text': "So I'm saying this place is 1 to 2.", 'start': 755.333, 'duration': 2.342}, {'end': 766.481, 'text': "So I'm saying 1 to 2 via 0, which means 1 to 0 plus 0 to 2.", 'start': 757.675, 'duration': 8.806}, {'end': 768.903, 'text': "Let's see the value of 1 to 0.", 'start': 766.481, 'duration': 2.422}, {'end': 770.084, 'text': '1 to 0 is 1.', 'start': 768.903, 'duration': 1.181}, {'end': 776.249, 'text': "So I'll just write 1 plus 0 to 2 plus 0 to 2 is infinity.", 'start': 770.084, 'duration': 6.165}, {'end': 779.971, 'text': "So that means it's an infinity which I do not need to write.", 'start': 776.949, 'duration': 3.022}], 'summary': 'Converting undirected graph to directed, calculating resultant matrix via vertex 0.', 'duration': 61.083, 'max_score': 626.227, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YbY8cVwWAvw/pics/YbY8cVwWAvw626227.jpg'}], 'start': 579.199, 'title': "Floyd's algorithm and shortest path analysis", 'summary': "Explains the derivation of initial cost matrix from a directed graph, demonstrates the conversion of undirected graph to directed graph for applying floyd's algorithm, and discusses calculation of shortest paths from a given vertex to all other vertices using specific vertices, resulting in path distances determination and optimization.", 'chapters': [{'end': 656.826, 'start': 579.199, 'title': "Floyd's algorithm in graphs", 'summary': "Explains the initial cost matrix derivation from a given directed graph, and demonstrates the conversion of an undirected graph to a directed graph in order to apply floyd's algorithm, with a mention of moving via vertex zero.", 'duration': 77.627, 'highlights': ['The initial cost matrix is derived from the given graph, with all other costs set to infinity, representing unreachable nodes.', 'Explanation of converting an undirected graph to a directed graph by splitting the edges and creating dual direction edges.', 'Demonstration of moving via vertex zero as the first step in the process.']}, {'end': 958.494, 'start': 656.826, 'title': 'Shortest path analysis', 'summary': 'Discusses the calculation of shortest paths from a given vertex to all other vertices in a graph using the method of moving via specific vertices, resulting in the determination of path distances and their optimization.', 'duration': 301.668, 'highlights': ['The chapter emphasizes the process of calculating the shortest paths from a given vertex to all other vertices in a graph, exemplified by the detailed analysis of moving via specific vertices and determining the resultant path distances.', 'The speaker illustrates the step-by-step computation of the shortest paths from vertex 0 to all other vertices, emphasizing the logic of moving via a particular root and the resultant path distance calculations, demonstrating the iterative process of evaluating and optimizing path distances.', 'The detailed analysis of moving via specific vertices, such as 0, 1, 2, and 3, showcases the systematic determination of path distances and the iterative optimization of path values by considering various possible routes and selecting the most efficient path options.', 'The explanation of the iterative calculation and optimization process for the shortest paths highlights the consideration of multiple routes, the comparison of path distances, and the selection of the most efficient path options based on the computed values and via-specific movements.']}], 'duration': 379.295, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YbY8cVwWAvw/pics/YbY8cVwWAvw579199.jpg', 'highlights': ['The explanation of converting an undirected graph to a directed graph by splitting the edges and creating dual direction edges.', 'The initial cost matrix is derived from the given graph, with all other costs set to infinity, representing unreachable nodes.', 'The chapter emphasizes the process of calculating the shortest paths from a given vertex to all other vertices in a graph, exemplified by the detailed analysis of moving via specific vertices and determining the resultant path distances.', 'The detailed analysis of moving via specific vertices, such as 0, 1, 2, and 3, showcases the systematic determination of path distances and the iterative optimization of path values by considering various possible routes and selecting the most efficient path options.']}, {'end': 1481.506, 'segs': [{'end': 1064.505, 'src': 'embed', 'start': 1039.15, 'weight': 4, 'content': [{'end': 1044.134, 'text': 'so zero, one means two plus one, two, one, two means three.', 'start': 1039.15, 'duration': 4.984}, {'end': 1046.636, 'text': 'so you get a three, which makes it five.', 'start': 1044.134, 'duration': 2.502}, {'end': 1048.538, 'text': 'what is the value already stored?', 'start': 1046.636, 'duration': 1.902}, {'end': 1051.38, 'text': 'infinity, you are reaching at a better position.', 'start': 1048.538, 'duration': 2.842}, {'end': 1054.003, 'text': "five, you go via when you're reaching at five.", 'start': 1051.38, 'duration': 2.623}, {'end': 1055.024, 'text': 'much better, much better.', 'start': 1054.003, 'duration': 1.021}, {'end': 1060.543, 'text': 'next, zero, three via one means zero.', 'start': 1056.081, 'duration': 4.462}, {'end': 1062.804, 'text': 'one is two plus one, three.', 'start': 1060.543, 'duration': 2.261}, {'end': 1064.505, 'text': "let's see the value of one, three.", 'start': 1062.804, 'duration': 1.701}], 'summary': 'The value stored is five, reaching a better position.', 'duration': 25.355, 'max_score': 1039.15, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YbY8cVwWAvw/pics/YbY8cVwWAvw1039150.jpg'}, {'end': 1234.303, 'src': 'embed', 'start': 1209.912, 'weight': 0, 'content': [{'end': 1221.037, 'text': 'you can figure out from every node one to every node, to the shortest path, from this ultimate matrix that has been generated.', 'start': 1209.912, 'duration': 11.125}, {'end': 1223.598, 'text': 'so what are we doing exactly?', 'start': 1221.037, 'duration': 2.561}, {'end': 1228.2, 'text': 'at first, we are going via 0, then via 1, then via 2, then via 3..', 'start': 1223.598, 'duration': 4.602}, {'end': 1234.303, 'text': "so can i say i'm going with everyone and whenever i'm going via zero, i'm basically taking this.", 'start': 1228.2, 'duration': 6.103}], 'summary': 'Analyzing shortest path using generated matrix, going via nodes 0 to 3.', 'duration': 24.391, 'max_score': 1209.912, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YbY8cVwWAvw/pics/YbY8cVwWAvw1209912.jpg'}, {'end': 1469.636, 'src': 'heatmap', 'start': 1358.577, 'weight': 0.971, 'content': [{'end': 1366.803, 'text': 'First get the via 0, via 1, via 2 and ultimately the cost of IGA will be storing your ultimate shortest distance.', 'start': 1358.577, 'duration': 8.226}, {'end': 1368.184, 'text': 'Now, couple of questions.', 'start': 1367.143, 'duration': 1.041}, {'end': 1372.107, 'text': 'First question is how to detect a negative cycle?', 'start': 1368.724, 'duration': 3.383}, {'end': 1375.069, 'text': 'What if the graph has a negative cycle?', 'start': 1372.367, 'duration': 2.702}, {'end': 1378.971, 'text': 'Because we know for a negative cycle.', 'start': 1375.089, 'duration': 3.882}, {'end': 1386.408, 'text': 'imagine a cycle like this where we say okay, takes minus two, minus three plus two.', 'start': 1378.971, 'duration': 7.437}, {'end': 1391.491, 'text': 'so the total costing is minus two plus two, minus three, minus two plus two guys goes.', 'start': 1386.408, 'duration': 5.083}, {'end': 1394.573, 'text': 'so total costing is minus three.', 'start': 1391.491, 'duration': 3.082}, {'end': 1404.478, 'text': 'so what will happen is the floyd version will work properly and it will figure out a path via one, two to reach zero.', 'start': 1394.573, 'duration': 9.905}, {'end': 1409.78, 'text': 'so the costing of zero and zero will be minus three.', 'start': 1404.478, 'duration': 5.302}, {'end': 1419.325, 'text': 'and apparently the costing of any given node to itself should be zero, because this node to node should always be zero.', 'start': 1409.78, 'duration': 9.545}, {'end': 1431.271, 'text': "and if it is anything lesser to zero, if the costing of any node, can i say this if the costing of any node from zero to n, it's very simple.", 'start': 1419.325, 'duration': 11.946}, {'end': 1441.477, 'text': 'if the costing of i and i, which is the node to node itself, is lesser than zero, i can always say negative cycle exist.', 'start': 1431.271, 'duration': 10.206}, {'end': 1444.758, 'text': 'i can always say negative cycle exist.', 'start': 1441.477, 'duration': 3.281}, {'end': 1451.002, 'text': 'very simple, if we are going from, uh, all the nodes and node to node is lesser than zero,', 'start': 1444.758, 'duration': 6.244}, {'end': 1458.867, 'text': 'means floyd roshiel has gone via this and has reduced the cost from 0 to something lesser because of a negative cycle.', 'start': 1451.002, 'duration': 7.865}, {'end': 1463.091, 'text': "And you know, if it has a negative cycle, it doesn't make sense to find the shortest path,", 'start': 1459.168, 'duration': 3.923}, {'end': 1469.636, 'text': "because someone will do unlimited turns and you'll just reduce its cost every now and then.", 'start': 1463.091, 'duration': 6.545}], 'summary': 'Detect negative cycle: if node to node cost < 0, negative cycle exists.', 'duration': 111.059, 'max_score': 1358.577, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YbY8cVwWAvw/pics/YbY8cVwWAvw1358577.jpg'}, {'end': 1469.636, 'src': 'embed', 'start': 1441.477, 'weight': 1, 'content': [{'end': 1444.758, 'text': 'i can always say negative cycle exist.', 'start': 1441.477, 'duration': 3.281}, {'end': 1451.002, 'text': 'very simple, if we are going from, uh, all the nodes and node to node is lesser than zero,', 'start': 1444.758, 'duration': 6.244}, {'end': 1458.867, 'text': 'means floyd roshiel has gone via this and has reduced the cost from 0 to something lesser because of a negative cycle.', 'start': 1451.002, 'duration': 7.865}, {'end': 1463.091, 'text': "And you know, if it has a negative cycle, it doesn't make sense to find the shortest path,", 'start': 1459.168, 'duration': 3.923}, {'end': 1469.636, 'text': "because someone will do unlimited turns and you'll just reduce its cost every now and then.", 'start': 1463.091, 'duration': 6.545}], 'summary': 'Negative cycle detection in graph using floyd-warshall algorithm to prevent infinite cost in finding shortest path.', 'duration': 28.159, 'max_score': 1441.477, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YbY8cVwWAvw/pics/YbY8cVwWAvw1441477.jpg'}], 'start': 959.295, 'title': 'Route values and shortest paths', 'summary': 'Discusses computing route values and evaluating their optimality, while also explaining the process of computing the shortest path between nodes using matrix operations, resulting in the shortest path matrix. it also covers detecting negative cycles in graphs using the floyd-warshall algorithm and their impact on finding the shortest path.', 'chapters': [{'end': 1160.431, 'start': 959.295, 'title': 'Computing route values', 'summary': 'Discusses computing route values by traversing different paths and reaching specific destinations, with the final route values being computed and evaluated for optimality, resulting in better positions.', 'duration': 201.136, 'highlights': ['The value of 3, 0 is 3, and reaching three via the previous routes is better than the new upgraded version, which has a value of 6.', 'The value of 3, 1 is 5, and adding 1, 0 yields a value of 6, but reaching three via the previous routes is better, with a value of 3.', "Reaching five via a specific route is deemed much better, with a value of 5, compared to the previous route's value of infinity, demonstrating the evaluation of optimal route values."]}, {'end': 1358.217, 'start': 1160.431, 'title': 'Shortest path computation via matrix', 'summary': 'Explains the process of computing the shortest path between nodes using matrix operations, iterating through each node and storing the minimum costs, ultimately resulting in the shortest path matrix.', 'duration': 197.786, 'highlights': ['The chapter explains the process of computing the shortest path between nodes using matrix operations The speaker describes the method of computing the shortest path between nodes using matrix operations, providing a fundamental understanding of the process.', 'Iterating through each node and storing the minimum costs The method involves iterating through each node and storing the minimum costs, demonstrating a systematic approach to finding the shortest path.', 'Ultimately resulting in the shortest path matrix The iterative process leads to the generation of the ultimate matrix, which represents the shortest path between every pair of nodes, providing a tangible outcome of the computation.']}, {'end': 1481.506, 'start': 1358.577, 'title': 'Detecting negative cycles in graphs', 'summary': 'Explains the concept of detecting negative cycles in graphs using floyd-warshall algorithm, with a detailed explanation of how to identify a negative cycle and its impact on finding the shortest path.', 'duration': 122.929, 'highlights': ['A negative cycle can be detected by checking if the cost of a node to itself is lesser than zero in the context of Floyd-Warshall algorithm. ', 'The presence of a negative cycle makes it impossible to find the shortest path as the cost can be reduced indefinitely due to the cycle. ', 'Understanding the concept of negative cycles is essential to avoid impractical or incorrect shortest path calculations in graph algorithms. ']}], 'duration': 522.211, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YbY8cVwWAvw/pics/YbY8cVwWAvw959295.jpg', 'highlights': ['The iterative process leads to the generation of the ultimate matrix, which represents the shortest path between every pair of nodes, providing a tangible outcome of the computation.', 'Understanding the concept of negative cycles is essential to avoid impractical or incorrect shortest path calculations in graph algorithms.', 'The chapter explains the process of computing the shortest path between nodes using matrix operations, providing a fundamental understanding of the process.', 'A negative cycle can be detected by checking if the cost of a node to itself is lesser than zero in the context of Floyd-Warshall algorithm.', "Reaching five via a specific route is deemed much better, with a value of 5, compared to the previous route's value of infinity, demonstrating the evaluation of optimal route values."]}, {'end': 1803.105, 'segs': [{'end': 1778.087, 'src': 'heatmap', 'start': 1727.403, 'weight': 0, 'content': [{'end': 1736.808, 'text': 'but if the graph does not have negative cycles or something, you can actually apply a dixtra for all the nodes, because dixtra in itself takes e,', 'start': 1727.403, 'duration': 9.405}, {'end': 1737.128, 'text': 'log v.', 'start': 1736.808, 'duration': 0.32}, {'end': 1748.506, 'text': 'so what you can do is apply dixtra on every individual node to find out the answer every individual node and there will still be n cross e log v,', 'start': 1737.128, 'duration': 11.378}, {'end': 1751.93, 'text': "so it'll still be less like v cross e log v.", 'start': 1748.506, 'duration': 3.424}, {'end': 1755.674, 'text': "it won't go till n cube, which the floyd motion is taking.", 'start': 1751.93, 'duration': 3.744}, {'end': 1759.859, 'text': 'apply individual dixtra on every node to get every pair distance.', 'start': 1755.674, 'duration': 4.185}, {'end': 1762.001, 'text': "you can do that, but it doesn't work for negative.", 'start': 1759.859, 'duration': 2.142}, {'end': 1766.816, 'text': 'Now, if in an interview someone does ask you about Floyd Walsh, do not just tell the algorithm.', 'start': 1763.072, 'duration': 3.744}, {'end': 1770.739, 'text': 'Tell about these extra things like why does something like a Dijkstra will not work?', 'start': 1767.056, 'duration': 3.683}, {'end': 1773.262, 'text': 'How can you detect a negative cycle?', 'start': 1771.961, 'duration': 1.301}, {'end': 1778.087, 'text': "If you add up these extra points in an interview, it's always a cherry on the cake.", 'start': 1773.562, 'duration': 4.525}], 'summary': "Using dijkstra on each node reduces time complexity to n * e * log v, avoiding n^3 as with floyd-warshall. mentioning additional points like why dijkstra won't work and detecting negative cycles can enhance interviews.", 'duration': 45.859, 'max_score': 1727.403, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YbY8cVwWAvw/pics/YbY8cVwWAvw1727403.jpg'}], 'start': 1481.906, 'title': 'Shortest distance in directed graph', 'summary': "Discusses the floyd-warshall algorithm for finding the shortest distance between every pair of vertices in a given edge-weighted directed graph with a time complexity of o(n^3) and a space complexity of o(n^2), along with limitations of dijkstra's algorithm and detection of negative cycles.", 'chapters': [{'end': 1803.105, 'start': 1481.906, 'title': 'Shortest distance in directed graph', 'summary': "Discusses the floyd-warshall algorithm for finding the shortest distance between every pair of vertices in a given edge-weighted directed graph, with a time complexity of o(n^3) and a space complexity of o(n^2). it also touches on the limitations of dijkstra's algorithm and the detection of negative cycles.", 'duration': 321.199, 'highlights': ["The Floyd-Warshall algorithm has a time complexity of O(n^3). The algorithm's time complexity is O(n^3), making it efficient for finding the shortest distance between every pair of vertices in a directed graph.", 'The space complexity of the Floyd-Warshall algorithm is O(n^2). The space complexity of the algorithm is O(n^2) due to the use of the given matrix for solving the problem.', "Dijkstra's algorithm cannot be implemented for graphs with negative cycles. Dijkstra's algorithm is not suitable for graphs with negative cycles and will result in a time limit exceeded (TLE) error.", "Applying Dijkstra on every individual node can yield a time complexity of n * e * log(v). By applying Dijkstra's algorithm on each node individually, the time complexity can be reduced to n * e * log(v) for finding the shortest distance for every pair of vertices.", "Understanding the limitations of Dijkstra's algorithm and how to detect negative cycles adds value in an interview. Explaining the limitations of Dijkstra's algorithm and the methods for detecting negative cycles can enhance the discussion on the Floyd-Warshall algorithm in an interview setting."]}], 'duration': 321.199, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/YbY8cVwWAvw/pics/YbY8cVwWAvw1481906.jpg', 'highlights': ['The Floyd-Warshall algorithm has a time complexity of O(n^3).', 'The space complexity of the Floyd-Warshall algorithm is O(n^2).', "Understanding the limitations of Dijkstra's algorithm and how to detect negative cycles adds value in an interview.", 'Applying Dijkstra on every individual node can yield a time complexity of n * e * log(v).', "Dijkstra's algorithm cannot be implemented for graphs with negative cycles."]}], 'highlights': ['The Floyd-Warshall algorithm has a time complexity of O(n^3).', 'The space complexity of the Floyd-Warshall algorithm is O(n^2).', 'The iterative process leads to the generation of the ultimate matrix, which represents the shortest path between every pair of nodes, providing a tangible outcome of the computation.', 'Understanding the concept of negative cycles is essential to avoid impractical or incorrect shortest path calculations in graph algorithms.', 'A negative cycle can be detected by checking if the cost of a node to itself is lesser than zero in the context of Floyd-Warshall algorithm.', 'The algorithm helps detect negative cycles in a graph. It aids in identifying negative cycles within the graph, providing a solution for graphs containing negative cycles.', 'The explanation of converting an undirected graph to a directed graph by splitting the edges and creating dual direction edges.', 'The initial cost matrix is derived from the given graph, with all other costs set to infinity, representing unreachable nodes.', 'The chapter emphasizes the process of calculating the shortest paths from a given vertex to all other vertices in a graph, exemplified by the detailed analysis of moving via specific vertices and determining the resultant path distances.', 'The detailed analysis of moving via specific vertices, such as 0, 1, 2, and 3, showcases the systematic determination of path distances and the iterative optimization of path values by considering various possible routes and selecting the most efficient path options.']}