{\displaystyle O(|V||E|)} Bellman-Ford algorithm is a single source shortest path algorithm that finds the shortest path from the source vertex to all other vertices in a given weighted graph. k The current distance from the source to A is infinity. -, -, Gi s v l nh lin ngay trc u trn ng i ny. A gloomy graph is what I call a graph with negative weights. ins.style.display='block';ins.style.minWidth=container.attributes.ezaw.value+'px';ins.style.width='100%';ins.style.height=container.attributes.ezah.value+'px';container.appendChild(ins);(adsbygoogle=window.adsbygoogle||[]).push({});window.ezoSTPixelAdd(slotId,'stat_source_id',44);window.ezoSTPixelAdd(slotId,'adsensetype',1);var lo=new MutationObserver(window.ezaslEvent);lo.observe(document.getElementById(slotId+'-asloaded'),{attributes:true}); Relaxing means trying to lower the cost of getting to a vertex by using another vertex. Consider the edge (D, F). The distance to A is currently -2, so the distance to B via edge A-B is -2 + 5 = 3. Mi nt tnh khong cch gia n v tt c cc nt khc trong h thng t ch v lu tr thng tin ny trong mt bng. ( | The algorithm then iterates over all edges in the graph V-1 times, where V is the number of vertices in the graph. {\displaystyle O(k|E|)} would appear. The next edge is (3, 2). Since (0 + 4) is greater than 2 so there would be no updation. The Bellman-Ford algorithm is an algorithm similar to Dijkstra that is it finds the shortest path in a graph from a single source vertex to all other vertices in a weighted graph but it works even when there are negative weights. 2 Dijkstra's Correctness In the previous lecture, we introduced Dijkstra's algorithm, which, given a positive-weighted graph G = Khi , phn ng i t ngun ti v l ng i ngn nht t ngun ti v qua ti a i-1 cung. The `main` function creates a graph with the specified number of vertices and edges and adds the edges to the graph. But if optimal time is not the highest priority then no doubt Bellman Ford is a better shortest path algorithm. Since (2 + 7) equals to 9 which is less than 10 so update: The next edge is (4, 3). Now, again we will check all the edges. Bellman Ford is an algorithm used to compute single source shortest path. Dijkstras cant work on this problem then. 67 courses. Pred The predecessor to F is B. Edges C-B and C-H yield the same results, so the table remains the same. The first edge is (1, 3). For example, if we run the Bellman-Ford algorithm with A as the source vertex in the following graph, it will produce the shortest distance from the source vertex to all other vertices of the graph (vertex B and C): The Belman algorithm works similar to Dijkstras algorithm, however, it can handle graphs with negative-weighted edges. Consider the edge (B, E). the penultimate vertex in the shortest path leading to it. ( Although it has some disadvantages such as a slower time complexity and the possibility of not terminating if the graph contains a negative cycle, it has many use cases in various fields such as transportation, computer networking, and finance. For n vertices, we relax the edges for n-1 times where n is the number of edges. Consider a scenario, in which each edge has a negative edge weight, we can apply the Bellman-Ford algorithm. On the other hand, Dijkstra's algorithm cannot work with graphs with negative edge weights. The distance to vertex G is 6, so the distance to B is 6 + 4 = 10. During the second iteration, all of the edges are examined again. Bellman ford algorithm is a single-source shortest path algorithm. His background consists of creating enterprise level e-commerce applications, performing research based software development, and facilitating the spread of knowledge through writing. The case of presence of a negative weight cycle will be discussed below in a separate section. T 1 nh xut pht nhn hnh ta c th suy ra ng i ngn nht t nh ti cc nh khc m khng cn lm li t u. ( {\displaystyle O(|V|\cdot |E|)} In computer science, algorithms are essential tools that help solve complex problems in a structured and efficient way. Looking at edges B-F, C-B, C-H, F-G, G-B, and H-D, we can see that they all yield the same result, infinity. Nu tn ti chu trnh m m t nh ngun c th i n c th s khng tn ti ng i nh nht (v mi ln i quanh chu trnh m l mt ln gim trng s ca ng). Taking an example, we are gonna go through a few steps to understand the functioning. 41-47, 2012. The table with the distances and the predecessors is constructed. Then it iteratively relaxes those estimates by finding new paths that are shorter than the previously overestimated paths. The most commonly used algorithm is Dijkstra's algorithm. Denote vertex 'A' as 'u' and vertex 'D' as 'v'. 155,738 students. Bellman-Ford algorithm can also work with a non-negative undirected graph, but it can only handle negative edges in a directed graph. Now use the relaxing formula: Therefore, the distance of vertex B is 1. So a Negative cycle becomes a cycle that sums up to a negative value. Mail us on [emailprotected], to get more information about given services. Since (0 + 5) equals to 5 which is greater than -5 so there would be no updation in the vertex 3. The Bellman-Ford algorithm is an extension of Dijkstra's algorithm which calculates the briefest separation from the source highlight the entirety of the vertices. 20 is a reduced value from the earlier 25. The distance to B is 9, so the distance to vertex F is 9 + (-5) = 4. v Since (-5 + 7) equals to 2 which is less than 3 so update: The next edge is (2, 4). It repetitively loops over all the edges and updates the distances at the start node, the same as in Dijkstra's algorithm. Dist Denote vertex '3' as 'u' and vertex '2' as 'v'. ( Ch rng c th kt lun c th c chu trnh m hay khng. Edge B-C can be reached in 6 + 2 = 8. Find the shortest path in a graph having non-negative edges weight is an NP-hard problem. The `createGraph` function creates a new graph with V vertices and E edges. 1 In this tutorial, we learned what the Bellman-Ford algorithm is, how it works, and how to implement Bellman-Ford algorithm in C++, Java, and Python to find the cost of the path. The current distance to B is 3, so the distance to C is 3 + 2 = 5. | Though it is slower than Dijkstra's algorithm, Bellman . It finds a global optimum solution and so if there is a negative cycle, the algorithm will keep ongoing indefinitely. The Bellman-Ford algorithm is a single-source shortest path algorithm. E One such algorithm is the Bellman-Ford Algorithm, which is used to find the shortest path between two nodes in a weighted graph. During the fourth iteration, all the edges are examined. Data Structures & Algorithms Multiple Choice Questions on "Bellman-Ford Algorithm". In the presence of a negative cycle(s), there are further complications associated with the fact that distances to all vertices in this cycle, as well as the distances to the vertices reachable from this cycle is not defined they should be equal to minus infinity $(- \infty)$. Consider the edge (1, 2). After applying Bellman-Ford algorithm on a graph, each vertex maintains the weight of the shortest path from the source . 4/07/05CS 5633 Analysis of Algorithms 13 Correctness Theorem. The algorithm may not terminate if the graph contains a negative cycle. The shortest path problem is about finding a path between $$2$$ vertices in a graph such that the total sum of the edges weights is minimum. He has over a decade of software engineering experience. ) In dynamic programming, there are many algorithms to find the shortest path in a graph.Some of them are Dijkstra's algorithm, BFS, DFS, Floyd, all-pair shortest path problem, and bidirectional algorithm.The most commonly used algorithm is Dijkstra's algorithm. Unlike many other graph algorithms, for Bellman-Ford algorithm, it is more convenient to represent the graph using a single list of all edges (instead of $n$ lists of edges - edges from each vertex). This is something that even the Bellman ford algorithm cant defeat. Denote vertex '1' as 'u' and vertex '2' as 'v'. Quarterly of Applied Mathematics 27: 526-530, 1970. This algorithm is used to find the shortest distance from the single vertex to all the other vertices of a weighted graph. Now use the relaxing formula: Therefore, the distance of vertex B is 6. Denote vertex '2' as 'u' and vertex '4' as 'v'. Due to the presence of a negative cycle, for $n$ iterations of the algorithm, the distances may go far in the negative range (to negative numbers of the order of $-n m W$, where $W$ is the maximum absolute value of any weight in the graph). Do leave some feedback, I am really looking forward to it. In any given graph, the shortest path between two any two vertices can include a maximum of V vertices (i.e. Now use the relaxing formula: Therefore, the distance of vertex 3 is 5. The Bellman-Ford Algorithm is a single-source shortest-path algorithm that finds the shortest path from a source vertex to all other vertices in a weighted graph. The next edge is (3, 2). 1. The working of the Bellman-Ford algorithm is the same as Dijkstra's algorithm. in Computer Science and a minor in Biology. | Consider the below graph. The algorithm bears the name of two American scientists: Richard Bellman and Lester Ford. The time complexity of Bellman ford is higher than that of Djikstra. Lester Ford Moore-Bellman-Ford Edward F. Moore | | . But at the end of the final iteration step, the algorithm would give you the shortest distance for each of the nodes from the source node. } When -3 is added to infinity, the result is infinity, so the value of C remains infinity. This set of MCQ on minimum spanning trees and algorithms in data structure includes multiple-choice questions on the design of minimum spanning trees, kruskal's algorithm, prim's algorithm, dijkstra and bellman-ford algorithms. Bellman-Ford algorithm finds all shortest path lengths from a source s V to all v V or determines that a negative weight cycle exists. Output The shortest paths from start to all other vertices. Dijkstra's algorithm and reaching Here it comes. Since (-4 + 7) equals to 3 which is less than 4 so update: The next edge is (2, 4). In this case, the algorithm will keep updating the estimates of the shortest path indefinitely. In such a case the algorithm will be terminated. So it's necessary to identify these cycles. The weight of edge A-C is -3. About Press Copyright Contact us Creators Advertise Developers Terms Privacy Policy & Safety How YouTube works Test new features NFL Sunday Ticket Press Copyright . SPFA is a improvement of the Bellman-Ford algorithm which takes advantage of the fact that not all attempts at relaxation will work. The main difference between this algorithm with Dijkstra's the algorithm is, in Dijkstra's algorithm we cannot handle the negative weight, but here we can handle it easily. [ | The next edge is (3, 2). {\displaystyle |V|-1} A negative weight is just like a positive weight, a value on the top of an edge. [3]. | Edge C-A is examined next. Nhc im chnh ca thut ton Bellman-Ford trong cu hnh ny l, Tm ng i ngn nht t nh B ti nh D ca th G dijkstraShortestPath (n, dist, next, start) Input Total number of nodes n, distance list for each vertex, next list to store which node comes next, and the seed or start vertex. We have already gone through the main differences that are, The difference that we havent touched so far is. i A cycle is a path where the first and the last vertex is the same, that is, it is a closed path. After determining the cost of 3, we take the next edges, which are 3 2 and 24. | The Bellman-Ford algorithm seeks to solve the single-source shortest path problem. Consider the edge (C, E). , - Looking at the table containing the edges, we start by relaxing edge A-C. This is not possible with some other shortest path algorithms, such as Dijkstras Algorithm, which requires that all edge weights be non-negative. The router shares the information between the neighboring node containing a direct link. Given a graph and a source vertex src in graph, find shortest paths from src to all vertices in the given graph. Updated on Mar 22, 2021. Now use the relaxing formula: Therefore, the distance of vertex D is 5. i) sort the edges of G in . We have created the following table for distance updation. Consider the edge (2, 4). Bellman-Ford Algorithm Java. Ford actually invented this algorithm in 1956 during the study of another mathematical problem, which eventually reduced to a subproblem of finding the shortest paths in the graph, and Ford gave an outline of the algorithm to solve this problem. 1 Hence we obtain the criterion for presence of a cycle of negative weights reachable for source vertex $v$: after $(n-1)_{th}$ phase, if we run algorithm for one more phase, and it performs at least one more relaxation, then the graph contains a negative weight cycle that is reachable from $v$; otherwise, such a cycle does not exist. Now use the relaxing formula: Since (5 + 7) is greater than 4, so there would be no updation in the vertex 2. {\displaystyle \Pi (k,i)=\min(\{\Pi (k-1,i)\}\cup \{\Pi (k-1,j)+L[j][i]\})}. Khi mt nt nhn c cc bng thng tin t cc nt ln cn, n tnh cc tuyn ng ngn nht ti tt c cc nt khc v cp nht bng thng tin ca chnh mnh. | https://mathworld.wolfram.com/Bellman-FordAlgorithm.html, https://mathworld.wolfram.com/Bellman-FordAlgorithm.html. Bellman-Ford algorithm starts with the initialization process. The time complexity of the unoptimized Bellman-Ford algorithm is easy to determine. Dijkstra's Algorithm. We start the implementation with a structure $\rm edge$ for representing the edges. During each iteration, the specific edge is relaxed. In this graph, 0 is considered as the source vertex. The distance to B is updated to 0. The loop will iterate 5 times to get the correct answer. Bellman This Applet demonstrates the Bellman-Ford Algorithm. However, if the graph contains a negative cycle, then, clearly, the shortest path to some vertices may not exist (due to the fact that the weight of the shortest path must be equal to minus infinity); however, this algorithm can be modified to signal the presence of a cycle of negative weight, or even deduce this cycle. In order to find the shortest path, first, we will initialize the source vertex (A) as 0 and other vertices with infinity (). Ez lassabb, mint Dijkstra algoritmusa ugyanarra a problmra, viszont sokoldalbb, mert kpes olyan grafikonok kezelsre, amelyekben az egyes lslyok negatv szmok. This makes it less efficient than other shortest path algorithms such as Dijkstras Algorithm, which has a time complexity of O(E log V) for a graph with non-negative edge weights. Denote vertex 'C' as 'u' and vertex 'E' as 'v'. Repeating this statement $k$ times, we see that after $k_{th}$ phase the distance to the vertex $p_k = a$ gets calculated correctly, which we wanted to prove. vv11 vv22 vv33 vvkk vv00 s v p: Since p is a shortest path, we have (s, vi) = (s, vi-1 . In contrast to Dijkstra's algorithm and the A* algorithm, the Bellman-Ford Algorithm also return shortest paths when negative edge weights are present. min E The next edge is (A, C). The time complexity of Bellman ford algorithm would be O(E|V| - 1). When expanded it provides a list of search options that will switch the search inputs to match the current selection. Let's now look into the relaxation equation which is the most important thing in this algorithm . E However be careful, because this algorithm is deterministic and it is easy to create counterexamples that make the algorithm run in $O(n m)$. So, we conclude that the bellman ford algorithm does not work when the graph contains the negative weight cycle. During the third iteration, the Bellman-Ford algorithm examines all the edges again. Since there are 9 edges, there will be up to 9 iterations. This algorithm can be somewhat speeded up: often we already get the answer in a few phases and no useful work is done in remaining phases, just a waste visiting all edges. One of the unique features of the Bellman-Ford Algorithm is that it can handle negative edge weights. k } Negative weights can explain a lot of phenomena, like your savings where a positive edge can represent money spent but a negative edge will be the one you would want to take as it will represent cash gained, or heat reactions, where each positive weight will stand for heat dissipation, each negative weight will show heat absorption and the set of reaction where minimum energy is found has to be calculated. O Consider the edge (E, F). The Bellman-Ford algorithm will iterate through each of the edges. Method 2: Implementation of Bellmanford Algorithm. IT Leader with a B.S. Although each edge is relaxed, the only edges that matter are the edges from S and from A since the distance to those vertices is already known. It can be used in finance to calculate the optimal route for a trader to buy and sell financial assets. In simpler terms, let V be the number of vertices, E be the number of edges, S be the starting node, and D be an array which tracks the best distance between the source node and rest vertices. The minimum time it takes for all nodes to receive the signal is 2. a) Boolean. But what if there are negative weights included? This means that, given a weighted graph, this algorithm will output the shortest distance from a selected node to all other nodes. Now use the relaxing formula: Therefore, the distance of vertex F is 4. As we have already reached an optimized value already, so if we can relax an edge again that means we have encountered a negative cycle. Therefore, at the time of improvement we just need to remember $p[ ]$, i.e, the vertex from which this improvement has occurred. The `Edge` struct is defined to represent a weighted edge. Now use the relaxing formula: Therefore, the distance of vertex 2 is 4. Lets look at a quick example. Now another point of optimization to notice carefully. To avoid this, it is possible to create a counter that stores how many times a vertex has been relaxed and stop the algorithm as soon as some vertex got relaxed for the $n$-th time. If the distance varies, it means that the bellman ford algorithm is not providing the correct answer. Other algorithms that can be used for this purpose include ( V All the vertices are numbered $0$ to $n - 1$. Create another loop to go through each edge (u, v) in E and do the following: | | This vertex will either lie in a negative weight cycle, or is reachable from it. Djikstra is fast. The process of relaxing an edge involves comparing the distance to the source vertex plus the weight of the edge to the current estimate of the distance to the target vertex. This makes the value of 2 as ( 35 -15)=20 and the value of 4 as 100. Similarly, taking the edge 54 totals the value of 4 to 60. Where |V| is number of vertices. Other algorithms that can be used for this purpose include Dijkstra's algorithm and reaching algorithm. Using vertex. O , trong V l s nh v E l s cung ca th. The Bellman-Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted graph. Denote vertex '4' as 'u' and vertex '3' as 'v'. Order of edges: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), (E, D). JavaTpoint offers college campus training on Core Java, Advance Java, .Net, Android, Hadoop, PHP, Web Technology and Python. Edge H-D can be relaxed since we know the distance to vertex H is -1. The number of iterations needed to find out the shortest path from source to all other vertices depends on the order that we select to relax the . During the first phase, the edge $(p_0,p_1)$ has been checked by the algorithm, and therefore, the distance to the vertex $p_1$ was correctly calculated after the first phase. -, - You know the source and need to reach all the other vertices through the shortest path. Since (5 - 2) equals to 3 so there would be no updation in the vertex C. The next edge is (D, F). Since (0 + 4) equals to 4 so there would be no updation in the vertex 2. ) If this graph had a negative cycle, after the iteration is repeated n-1 times, theoretically the Bellman-Ford algorithm should have found the shortest paths to all vertices. Ta s i tm ng i ngn nht t node 1 n cc node cn li . Tnh ng n ca thut ton c th c chng minh bng quy np. ) Parameters. The distance to vertex A is updated to -5 units. Table 1 shows Bellman -Ford algorithm [2] [3], whose input is a given graph G = (V, E), the edge weight setting cost, number of nodes n and the single source node v. The dist [u] to store the . Denote vertex '1' as 'u' and vertex '3' as 'v'. How Bellman Ford Algorithm works? : If G = (V, E) contains no negative- weight cycles, then after the Bellman-Ford algorithm executes, d[v] = (s, v) for all v V. Hence in the code, we adopted additional measures against the integer overflow as follows: The above implementation looks for a negative cycle reachable from some starting vertex $v$; however, the algorithm can be modified to just looking for any negative cycle in the graph. Edge F-G can now be relaxed. The limitation of the algorithm is that it cannot be applied if the graph has negative edge weights. And then it starts relaxing the estimates by discovering the new paths which are shorter than the previous ones. What do you do to solve this problem? Khi i bng s nh ca th, mi ng i tm c s l ng i ngn nht ton cc, tr khi th c chu trnh m. A. Now use the relaxing formula: Since (11 - 15) equals to -4 which is less than 5, so update. Now coming to your original question, yes Bellman Ford algorithm can relax the edges in any arbitrary order as nicely answered by @ead above. (Bellman Ford Algorithm) Bangla tutorial , Single source shortest path, From vertex B, we can move to vertex C, D and E. Calculate the distance from B to other vertices, we get. This process is followed by all the vertices for N-1 times for finding the . He also serves as the CEO at MyAutoSystem. However, unlike the Dijkstra Algorithm, the Bellman-Ford algorithm can work on graphs with . The algorithm has a time complexity of O(V*E), where V is the number of vertices and E is the number of edges in the graph. {\displaystyle k} A list of tasks that can be solved using the Bellman-Ford algorithm: See also the problem list in the article Finding the negative cycle in a graph. It is claimed that $n-1$ phases of the algorithm are sufficient to correctly calculate the lengths of all shortest paths in the graph (again, we believe that the cycles of negative weight do not exist). P I hope you guys liked this blog. According to this statement, the algorithm guarantees that after $k_{th}$ phase the shortest path for vertex $a$ will be found. The algorithm starts by setting the distance to the source vertex to zero and the distance to all other vertices to infinity. The predecessor of C is A. + If you liked what you read, check out my book, An Illustrative Introduction to Algorithms. The distance to all other vertices is infinity. Transcribed image text: (a) (10pt) Consider what happens when you run Bellman-Ford on the following graph, with the source being A. The predecessor of G is F. Edge G-B can now be relaxed. Edges A-C and A-E yield the same results. [ 1) This step initializes distances from source to all . You choose Dijkstras Algorithm. For this, it is sufficient to remember the last vertex $x$ for which there was a relaxation in $n_{th}$ phase. ] V While Dijkstra's algorithm simply works for edges with positive distances, Bellman Ford's algorithm works for negative distances also. In each pass, relax edges in the same order as in the figure, and show the d d and \pi values after each pass. Now, infinite levels are too high for us, stress is building up. Since ( 3+7) equals to 10 which is less than 11 so update. The Python implementation is very similar to the C++ and Java implementations. Edge B-F cannot be relaxed yet. ] Since (0 + 4) is greater than 3 so there would be no updation in the vertex C. The next edge is (A, D). | If we can, then there must be a negative-weight cycle in the graph, In Step 4, we print the shortest path from the source to all vertices in the graph using the, The Java implementation is very similar to the C++ implementation. In Step 1, we initialize distances from the source to all vertices as. We will create an array of distances $d[0 \ldots n-1]$, which after execution of the algorithm will contain the answer to the problem. Also, this cycle acts as a negative cycle because the total value sums up to a negative value -1. The Bellman-Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. Therefore, the distance of vertex 4 is 11. n The Bellman-Ford algorithm emulates the shortest paths from a single source vertex to all other vertices in a weighted digraph. {\displaystyle O(V\cdot E)} This list is a shortest path from $v$ to $t$, but in reverse order, so we call $\rm reverse()$ function over $\rm path$ and then output the path. To find the shortest path of the above graph, the first step is note down all the edges which are given below: (A, B), (A, C), (A, D), (B, E), (C, E), (D, C), (D, F), (E, F), (C, B). V After initialization, the algorithm relaxes all the edges of the graph |V-1| times. In fact, the shortest path to any vertex $a$ is a shortest path to some vertex $p[a]$, to which we added $a$ at the end of the path. Weisstein, Eric W. "Bellman-Ford Algorithm." If the loop is iterated more than 5 times then also the answer will be the same, i.e., there would be no change in the distance between the vertices. If we can, then there must be a negative-weight cycle in the graph. k Let us now prove the following assertion: After the execution of $i_{th}$ phase, the Bellman-Ford algorithm correctly finds all shortest paths whose number of edges does not exceed $i$. ( Yes I sneaked in a little history fact there!). Similarly, from A to E, the cost is 2, however, since the distance to A is infinity, the value of E remains infinity. After that, it is guaranteed that no relaxation will improve the distance to some vertex. V Since (5 + 3) equals to 8 which is greater than 4 so there would be no updation in the vertex F. The next edge is (C, B). Its not actually called this, but the name kind of suits, doesnt it? The `BellmanFord` function implements the Bellman-Ford algorithm to find the shortest path from source to all other vertices in the graph. In the same way, if we want to find the longest simple path from source (s) to vertex (v) and the graph has negative cycles, we cannot apply the Bellman-Ford algorithm. Another difference is that the Dijkstra algorithm looks only to the immediate neighbors of a vertex, Bellman-Ford goes through each edge in every iteration. In contrast to Dijkstra algorithm, bellman ford algorithm guarantees the correct answer even if the weighted graph contains the negative weight values. {\displaystyle D:{\texttt {Dist}}[v],P:{\texttt {Pred}}[v]}, https://zh.wikipedia.org/w/index.php?title=-&oldid=71758509. Let's understand this property through an example. The Bellman-Ford Algorithm works by repeatedly relaxing each edge in the graph, updating the estimated shortest path between the source vertex and all other vertices. Let's understand the algorithm with an example. Distance vector routing is a type of dynamic protocol. | The value at vertex E is 5. Follow. Consider the edge (A, B). This algorithm can be used on both weighted and unweighted graphs. Java. In fact, the shortest paths algorithms like Dijkstra's algorithm or Bellman-Ford algorithm give us a relaxing order. Problem "Parquet", Manacher's Algorithm - Finding all sub-palindromes in O(N), Burnside's lemma / Plya enumeration theorem, Finding the equation of a line for a segment, Check if points belong to the convex polygon in O(log N), Pick's Theorem - area of lattice polygons, Search for a pair of intersecting segments, Delaunay triangulation and Voronoi diagram, Half-plane intersection - S&I Algorithm in O(N log N), Strongly Connected Components and Condensation Graph, Dijkstra - finding shortest paths from given vertex, Floyd-Warshall - finding all shortest paths, Number of paths of fixed length / Shortest paths of fixed length, Minimum Spanning Tree - Kruskal with Disjoint Set Union, Second best Minimum Spanning Tree - Using Kruskal and Lowest Common Ancestor, Checking a graph for acyclicity and finding a cycle in O(M), Lowest Common Ancestor - Farach-Colton and Bender algorithm, Lowest Common Ancestor - Tarjan's off-line algorithm, Maximum flow - Ford-Fulkerson and Edmonds-Karp, Maximum flow - Push-relabel algorithm improved, Kuhn's Algorithm - Maximum Bipartite Matching, RMQ task (Range Minimum Query - the smallest element in an interval), Search the subsegment with the maximum/minimum sum, MEX task (Minimal Excluded element in an array), Optimal schedule of jobs given their deadlines and durations, 15 Puzzle Game: Existence Of The Solution, The Stern-Brocot Tree and Farey Sequences, E-OLYMP #1453 "Ford-Bellman" [difficulty: low], UVA #423 "MPI Maelstrom" [difficulty: low], UVA #10099 "The Tourist Guide" [difficulty: medium], Creative Commons Attribution Share Alike 4.0 International.