Misplaced Pages

#87912

71-499: Negative edge weights are found in various applications of graphs. This is why this algorithm is useful. If a graph contains a "negative cycle" (i.e. a cycle whose edges sum to a negative value) that is reachable from the source, then there is no cheapest path: any path that has a point on the negative cycle can be made cheaper by one more walk around the negative cycle. In such a case, the Bellman–Ford algorithm can detect and report

142-454: A tree . A chordless cycle in a graph, also called a hole or an induced cycle, is a cycle such that no two vertices of the cycle are connected by an edge that does not itself belong to the cycle. An antihole is the complement of a graph hole. Chordless cycles may be used to characterize perfect graphs : by the strong perfect graph theorem , a graph is perfect if and only if none of its holes or antiholes have an odd number of vertices that

213-407: A cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal. A graph without cycles is called an acyclic graph . A directed graph without directed cycles is called a directed acyclic graph . A connected graph without cycles is called

284-570: A hash table to store these values and test whether each subsequent value has already been stored. However, the space complexity of this algorithm is proportional to λ + μ , unnecessarily large. Additionally, to implement this method as a pointer algorithm would require applying the equality test to each pair of values, resulting in quadratic time overall. Thus, research in this area has concentrated on two goals: using less space than this naive algorithm, and finding pointer algorithms that use fewer equality tests. Floyd's cycle-finding algorithm

355-401: A priority queue to greedily select the closest vertex that has not yet been processed, and performs this relaxation process on all of its outgoing edges; by contrast, the Bellman–Ford algorithm simply relaxes all the edges, and does this | V | − 1 {\displaystyle |V|-1} times, where | V | {\displaystyle |V|}

426-744: A random permutation . This change makes the worst case for Yen's improvement (in which the edges of a shortest path strictly alternate between the two subsets E f and E b ) very unlikely to happen. With a randomly permuted vertex ordering, the expected number of iterations needed in the main loop is at most | V | / 3 {\displaystyle |V|/3} . Fineman (2023) , at Georgetown University , created an improved algorithm that with high probability, runs in O ( | V | 8 9 ⋅ | E | ) {\displaystyle O(|V|^{\frac {8}{9}}\cdot |E|)} time . Cycle (graph theory) In graph theory ,

497-547: A 32-bit integer). Upon the i {\displaystyle i} -th evaluation of the generator function, the algorithm compares the generated value with O ( log ⁡ i ) {\displaystyle O(\log i)} previous values; observe that i {\displaystyle i} goes up to at least μ + λ {\displaystyle \mu +\lambda } and at most μ + 2 λ {\displaystyle \mu +2\lambda } . Therefore,

568-474: A back edge, but finding any other already visited vertex will indicate a back edge. In the case of undirected graphs, only O ( n ) time is required to find a cycle in an n -vertex graph, since at most n  − 1 edges can be tree edges. Many topological sorting algorithms will detect cycles too, since those are obstacles for topological order to exist. Also, if a directed graph has been divided into strongly connected components , cycles only exist within

639-527: A collection of IP networks typically owned by an ISP. It consists of the following steps: The main disadvantages of the Bellman–Ford algorithm in this setting are as follows: The Bellman–Ford algorithm may be improved in practice (although not in the worst case) by the observation that, if an iteration of the main loop of the algorithm terminates without making any changes, the algorithm can be immediately terminated, as subsequent iterations will not make any more changes. With this early termination condition,

710-415: A constant-factor savings in time for dense graphs . This variation can be implemented by keeping a collection of vertices whose outgoing edges need to be relaxed, removing a vertex from this collection when its edges are relaxed, and adding to the collection any vertex whose distance value is changed by a relaxation step. In China, this algorithm was popularized by Fanding Duan, who rediscovered it in 1994, as

781-558: A cycle of the smallest possible length. In his 1736 paper on the Seven Bridges of Königsberg , widely considered to be the birth of graph theory, Leonhard Euler proved that, for a finite undirected graph to have a closed walk that visits each edge exactly once (making it a closed trail), it is necessary and sufficient that it be connected except for isolated vertices (that is, all edges are contained in one component) and have even degree at each vertex. The corresponding characterization for

SECTION 10

#1732851632088

852-409: A misattribution: Floyd describes algorithms for listing all simple cycles in a directed graph in a 1967 paper, but this paper does not describe the cycle-finding problem in functional graphs that is the subject of this article. In fact, Knuth's statement (in 1969), attributing it to Floyd, without citation, is the first known appearance in print, and it thus may be a folk theorem , not attributable to

923-501: A pointer to the next object in the sequence, or it may apply a subroutine for determining whether two of its pointers represent equal values in the sequence. The equality test action may involve some nontrivial computation: for instance, in Pollard's rho algorithm, it is implemented by testing whether the difference between two stored values has a nontrivial greatest common divisor with the number to be factored. In this context, by analogy to

994-428: A set of simple cycles that together cover each edge exactly once: this is Veblen's theorem . When a connected graph does not meet the conditions of Euler's theorem, a closed walk of minimum length covering each edge at least once can nevertheless be found in polynomial time by solving the route inspection problem . The problem of finding a single simple cycle that covers each vertex exactly once, rather than covering

1065-483: A single individual. The key insight in the algorithm is as follows. If there is a cycle, then, for any integers i ≥ μ and k ≥ 0 , x i = x i + kλ , where λ is the length of the loop to be found, μ is the index of the first element of the cycle, and k is a whole integer representing the number of loops. Based on this, it can then be shown that i = kλ ≥ μ for some k if and only if x i = x 2 i (if x i = x 2 i in

1136-460: A single outgoing edge) the vertices of which are the elements of S and the edges of which map an element to the corresponding function value, as shown in the figure. The set of vertices reachable from starting vertex x 0 form a subgraph with a shape resembling the Greek letter rho ( ρ ): a path of length μ from x 0 to a cycle of λ vertices. Generally, f will not be specified as

1207-569: A subsequent stage, and its steps involve only one evaluation of the function f rather than three. The following Python code shows how this technique works in more detail. Like the tortoise and hare algorithm, this is a pointer algorithm that uses O ( λ + μ ) tests and function evaluations and O (1) storage space. It is not difficult to show that the number of function evaluations can never be higher than for Floyd's algorithm. Brent claims that, on average, his cycle finding algorithm runs around 36% more quickly than Floyd's and that it speeds up

1278-419: A table of values, the way it is shown in the figure above. Rather, a cycle detection algorithm may be given access either to the sequence of values x i , or to a subroutine for calculating f . The task is to find λ and μ while examining as few values from the sequence or performing as few subroutine calls as possible. Typically, also, the space complexity of an algorithm for the cycle detection problem

1349-625: Is Θ ( log ⁡ ( μ + λ ) ) {\displaystyle \Theta (\log(\mu +\lambda ))} . This is under the usual assumption, present throughout this article, that the size of the function values is constant. Without this assumption, the space complexity is Ω ( log 2 ⁡ ( μ + λ ) ) {\displaystyle \Omega (\log ^{2}(\mu +\lambda ))} since we need at least μ + λ {\displaystyle \mu +\lambda } distinct values and thus

1420-493: Is a multiple of λ . Once ν is found, the algorithm retraces the sequence from its start to find the first repeated value x μ in the sequence, using the fact that λ divides ν and therefore that x μ = x μ + v . Finally, once the value of μ is known it is trivial to find the length λ of the shortest repeating cycle, by searching for the first position μ + λ for which x μ + λ = x μ . The algorithm thus maintains two pointers into

1491-503: Is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds. It is also called the "tortoise and the hare algorithm", alluding to Aesop's fable of The Tortoise and the Hare . The algorithm is named after Robert W. Floyd , who was credited with its invention by Donald Knuth . However, the algorithm does not appear in Floyd's published work, and this may be

SECTION 20

#1732851632088

1562-416: Is also correct because there is no path from source to u with 0 edges. For the inductive case, we first prove the first part. Consider a moment when a vertex's distance is updated by v.distance := u.distance + uv.weight . By inductive assumption, u.distance is the length of some path from source to u . Then u.distance + uv.weight is the length of the path from source to v that follows

1633-447: Is based on a different principle: searching for the smallest power of two 2 that is larger than both λ and μ . For i = 0, 1, 2, ... , the algorithm compares x 2 −1 with each subsequent sequence value up to the next power of two, stopping when it finds a match. It has two advantages compared to the tortoise and hare algorithm: it finds the correct length λ of the cycle directly, rather than needing to search for it in

1704-406: Is based on the idea of exponential search . Both Floyd's and Brent's algorithms use only a constant number of memory cells, and take a number of function evaluations that is proportional to the distance from the start of the sequence to the first repetition. Several other algorithms trade off larger amounts of memory for fewer function evaluations. The applications of cycle detection include testing

1775-405: Is greater than three. A chordal graph , a special type of perfect graph, has no holes of any size greater than three. The girth of a graph is the length of its shortest cycle; this cycle is necessarily chordless. Cages are defined as the smallest regular graphs with given combinations of degree and girth. A peripheral cycle is a cycle in a graph with the property that every two edges not on

1846-463: Is of importance: we wish to solve the problem while using an amount of memory significantly smaller than it would take to store the entire sequence. In some applications, and in particular in Pollard's rho algorithm for integer factorization , the algorithm has much more limited access to S and to f . In Pollard's rho algorithm, for instance, S is the set of integers modulo an unknown prime factor of

1917-528: Is smaller. Therefore, after i iterations, v.distance is at most the length of P , i.e., the length of the shortest path from source to v that uses at most i edges. If there are no negative-weight cycles, then every shortest path visits each vertex at most once, so at step 3 no further improvements can be made. Conversely, suppose no improvement can be made. Then for any cycle with vertices v [0], ..., v [ k −1], v[i].distance <= v[i-1 (mod k)].distance + v[i-1 (mod k)]v[i].weight Summing around

1988-520: Is that it never backs up to reevaluate the generator function, and is economical in both space and time. It could be roughly described as a concurrent version of Brent's algorithm. While Brent's algorithm gradually increases the gap between the tortoise and hare, Gosper's algorithm uses several tortoises (several previous values are saved), which are roughly exponentially spaced. According to the note in HAKMEM item 132, this algorithm will detect repetition before

2059-449: Is the algorithmic problem of finding a cycle in a sequence of iterated function values. For any function f that maps a finite set S to itself, and any initial value x 0 in S , the sequence of iterated function values must eventually use the same value twice: there must be some pair of distinct indices i and j such that x i = x j . Once this happens, the sequence must continue periodically , by repeating

2130-422: Is the maximum length of a shortest path in the graph. The correctness of the algorithm can be shown by induction : Lemma . After i repetitions of for loop, Proof . For the base case of induction, consider i=0 and the moment before for loop is executed for the first time. Then, for the source vertex, source.distance = 0 , which is correct. For other vertices u , u.distance = infinity , which

2201-404: Is the number of vertices in the graph. In each of these repetitions, the number of vertices with correctly calculated distances grows, from which it follows that eventually all vertices will have their correct distances. This method allows the Bellman–Ford algorithm to be applied to a wider class of inputs than Dijkstra's algorithm. The intermediate answers depend on the order of edges relaxed, but

Bellman–Ford algorithm - Misplaced Pages Continue

2272-413: Is visited in the order v 1 , v 2 , ..., v | V | , relaxing each outgoing edge from that vertex in E f . Each vertex is then visited in the order v | V | , v | V |−1 , ..., v 1 , relaxing each outgoing edge from that vertex in E b . Each iteration of the main loop of the algorithm, after the first one, adds at least two edges to the set of edges whose relaxed distances match

2343-489: The Pollard rho algorithm by around 24%. He also performs an average case analysis for a randomized version of the algorithm in which the sequence of indices traced by the slower of the two pointers is not the powers of two themselves, but rather a randomized multiple of the powers of two. Although his main intended application was in integer factorization algorithms, Brent also discusses applications in testing pseudorandom number generators. R. W. Gosper 's algorithm finds

2414-490: The cycle space ), which consists of the edge sets that have even degree at every vertex; it forms a vector space over the two-element field . By Veblen's theorem , every element of the cycle space may be formed as an edge-disjoint union of simple cycles. A cycle basis of the graph is a set of simple cycles that forms a basis of the cycle space. Using ideas from algebraic topology , the binary cycle space generalizes to vector spaces or modules over other rings such as

2485-425: The pointer machine model of computation, an algorithm that only uses pointer copying, advancement within the sequence, and equality tests may be called a pointer algorithm. If the input is given as a subroutine for calculating f , the cycle detection problem may be trivially solved using only λ + μ function applications, simply by computing the sequence of values x i and using a data structure such as

2556-432: The "shortest path faster algorithm". Yen (1970) described another improvement to the Bellman–Ford algorithm. His improvement first assigns some arbitrary linear order on all vertices and then partitions the set of all edges into two subsets. The first subset, E f , contains all edges ( v i , v j ) such that i < j ; the second, E b , contains edges ( v i , v j ) such that i > j . Each vertex

2627-510: The Bellman–Ford algorithm can be used for applications in which this is the target to be sought – for example in cycle-cancelling techniques in network flow analysis. A distributed variant of the Bellman–Ford algorithm is used in distance-vector routing protocols , for example the Routing Information Protocol (RIP). The algorithm is distributed because it involves a number of nodes (routers) within an Autonomous system (AS) ,

2698-435: The algorithm initializes the distance to the source to 0 and all other nodes to infinity. Then for all edges, if the distance to the destination can be shortened by taking the edge, the distance is updated to the new lower value. The core of the algorithm is a loop that scans across all edges at every loop. For every i ≤ | V | − 1 {\displaystyle i\leq |V|-1} , at

2769-527: The algorithm is to return early when an iteration of step 2 fails to relax any edges, which implies all shortest paths have been found, and therefore there are no negative cycles. In that case, the complexity of the algorithm is reduced from O ( | V | ⋅ | E | ) {\displaystyle O(|V|\cdot |E|)} to O ( l ⋅ | E | ) {\displaystyle O(l\cdot |E|)} where l {\displaystyle l}

2840-464: The components and not between them, since cycles are strongly connected. For directed graphs, distributed message-based algorithms can be used. These algorithms rely on the idea that a message sent by a vertex in a cycle will come back to itself. Distributed cycle detection algorithms are useful for processing large-scale graphs using a distributed graph processing system on a computer cluster (or supercomputer). Applications of cycle detection include

2911-493: The correct shortest path distances: one from E f and one from E b . This modification reduces the worst-case number of iterations of the main loop of the algorithm from | V | − 1 to | V | / 2 {\displaystyle |V|/2} . Another improvement, by Bannister & Eppstein (2012) , replaces the arbitrary linear order of the vertices used in Yen's second improvement by

Bellman–Ford algorithm - Misplaced Pages Continue

2982-400: The cycle can be connected by a path whose interior vertices avoid the cycle. In a graph that is not formed by adding one edge to a cycle, a peripheral cycle must be an induced cycle. The term cycle may also refer to an element of the cycle space of a graph. There are many cycle spaces, one for each coefficient field or ring. The most common is the binary cycle space (usually called simply

3053-407: The cycle, the v [ i ].distance and v [ i −1 (mod k )].distance terms cancel, leaving 0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight I.e., every cycle has nonnegative weight. When the algorithm is used to find shortest paths, the existence of negative cycles is a problem, preventing the algorithm from finding a correct answer. However, since it terminates upon finding a negative cycle,

3124-411: The cycle, then there exists some k such that 2 i = i + kλ , which implies that i = kλ ; and if there are some i and k such that i = kλ , then 2i = i + kλ and x 2 i = x i + kλ ). Thus, the algorithm only needs to check for repeated values of this special form, one twice as far from the start of the sequence as the other, to find a period ν of a repetition that

3195-441: The edge uv to this path to obtain a path with at most i edges that is strictly shorter than P —a contradiction. By inductive assumption, u.distance after i −1 iterations is at most the length of this path from source to u . Therefore, uv.weight + u.distance is at most the length of P . In the i iteration, v.distance gets compared with uv.weight + u.distance , and is set equal to it if uv.weight + u.distance

3266-421: The edges must be scanned | V | − 1 {\displaystyle |V|-1} times to ensure the shortest path has been found for all nodes. A final scan of all the edges is performed and if any distance is updated, then a path of length | V | {\displaystyle |V|} edges has been found which can only occur if at least one negative cycle exists in

3337-463: The edges, is much harder. Such a cycle is known as a Hamiltonian cycle , and determining whether it exists is NP-complete . Much research has been published concerning classes of graphs that can be guaranteed to contain Hamiltonian cycles; one example is Ore's theorem that a Hamiltonian cycle can always be found in a graph for which every non-adjacent pair of vertices have degrees summing to at least

3408-491: The end of the i {\displaystyle i} -th iteration, from any vertex v , following the predecessor trail recorded in predecessor yields a path that has a total weight that is at most distance[v] , and further, distance[v] is a lower bound to the length of any path from source to v that uses at most i edges. Since the longest possible path without a cycle can be | V | − 1 {\displaystyle |V|-1} edges,

3479-407: The existence of a closed walk visiting each edge exactly once in a directed graph is that the graph be strongly connected and have equal numbers of incoming and outgoing edges at each vertex. In either case, the resulting closed trail is known as an Eulerian trail . If a finite undirected graph has even degree at each of its vertices, regardless of whether it is connected, then it is possible to find

3550-401: The final answer remains the same. Bellman–Ford runs in O ( | V | ⋅ | E | ) {\displaystyle O(|V|\cdot |E|)} time , where | V | {\displaystyle |V|} and | E | {\displaystyle |E|} are the number of vertices and edges respectively. Simply put,

3621-423: The function values are 32-bit integers and the second iteration of the cycle ends after at most 2 function evaluations since the beginning (viz. μ + 2 λ ≤ 2 32 {\displaystyle \mu +2\lambda \leq 2^{32}} ). Then Gosper's algorithm will find the cycle after at most 2 function evaluations, while consuming the space of 33 values (each value being

SECTION 50

#1732851632088

3692-525: The given sequence, one (the tortoise) at x i , and the other (the hare) at x 2 i . At each step of the algorithm, it increases i by one, moving the tortoise one step forward and the hare two steps forward in the sequence, and then compares the sequence values at these two pointers. The smallest value of i > 0 for which the tortoise and hare point to equal values is the desired value ν . The following Python code shows how this idea may be implemented as an algorithm. This code only accesses

3763-450: The graph. The edge (u, v) that is found in step 3 must be reachable from a negative cycle, but it isn't necessarily part of the cycle itself, which is why it's necessary to follow the path of predecessors backwards until a cycle is detected. The above pseudo-code uses a Boolean array ( visited ) to find a vertex on the cycle, but any cycle finding algorithm can be used to find a vertex on the cycle. A common improvement when implementing

3834-406: The integers, rational or real numbers, etc. The existence of a cycle in directed and undirected graphs can be determined by whether a depth-first search (DFS) finds an edge that points to an ancestor of the current vertex (i.e., it contains a back edge ). All the back edges which DFS skips over are part of cycles. In an undirected graph, the edge to the parent of a node should not be counted as

3905-442: The main loop may in some cases use many fewer than | V | − 1 iterations, even though the worst case of the algorithm remains unchanged. The following improvements all maintain the O ( | V | ⋅ | E | ) {\displaystyle O(|V|\cdot |E|)} worst-case time complexity. A variation of the Bellman–Ford algorithm described by Moore (1959) , reduces

3976-438: The negative cycle. Like Dijkstra's algorithm , Bellman–Ford proceeds by relaxation , in which approximations to the correct distance are replaced by better ones until they eventually reach the solution. In both algorithms, the approximate distance to each vertex is always an overestimate of the true distance, and is replaced by the minimum of its old value and the length of a newly found path. However, Dijkstra's algorithm uses

4047-445: The number of relaxation steps that need to be performed within each iteration of the algorithm. If a vertex v has a distance value that has not changed since the last time the edges out of v were relaxed, then there is no need to relax the edges out of v a second time. In this way, as the number of vertices with correct distance values grows, the number whose outgoing edges that need to be relaxed in each iteration shrinks, leading to

4118-504: The number to be factorized, so even the size of S is unknown to the algorithm. To allow cycle detection algorithms to be used with such limited knowledge, they may be designed based on the following capabilities. Initially, the algorithm is assumed to have in its memory an object representing a pointer to the starting value x 0 . At any step, it may perform one of three actions: it may copy any pointer it has to another object in memory, it may apply f and replace any of its pointers by

4189-484: The path from source to u and then goes to v . For the second part, consider a shortest path P (there may be more than one) from source to v with at most i edges. Let u be the last vertex before v on this path. Then, the part of the path from source to u is a shortest path from source to u with at most i-1 edges, since if it were not, then there must be some strictly shorter path from source to u with at most i-1 edges, and we could then append

4260-583: The period λ {\displaystyle \lambda } , and the lower and upper bound of the starting point, μ l {\displaystyle \mu _{l}} and μ u {\displaystyle \mu _{u}} , of the first cycle. The difference between the lower and upper bound is of the same order as the period, i.e. μ l + λ ∼ μ h {\displaystyle \mu _{l}+\lambda \sim \mu _{h}} . The main feature of Gosper's algorithm

4331-477: The previously-computed values. In order to do so quickly, they typically use a hash table or similar data structure for storing the previously-computed values, and therefore are not pointer algorithms: in particular, they usually cannot be applied to Pollard's rho algorithm. Where these methods differ is in how they determine which values to store. Following Nivasch, we survey these techniques briefly. Any cycle detection algorithm that stores at most M values from

SECTION 60

#1732851632088

4402-450: The quality of pseudorandom number generators and cryptographic hash functions , computational number theory algorithms, detection of infinite loops in computer programs and periodic configurations in cellular automata , automated shape analysis of linked list data structures, and detection of deadlocks for transactions management in DBMS . The figure shows a function f that maps

4473-425: The same sequence of values from x i to x j − 1 . Cycle detection is the problem of finding i and j , given f and x 0 . Several algorithms are known for finding cycles quickly and with little memory. Robert W. Floyd 's tortoise and hare algorithm moves two pointers at different speeds through the sequence of values until they both point to equal values. Alternatively, Brent's algorithm

4544-402: The sequence by storing and copying pointers, function evaluations, and equality tests; therefore, it qualifies as a pointer algorithm. The algorithm uses O ( λ + μ ) operations of these types, and O (1) storage space. Richard P. Brent described an alternative cycle detection algorithm that, like the tortoise and hare algorithm, requires only two pointers into the sequence. However, it

4615-402: The set S = {0,1,2,3,4,5,6,7,8} to itself. If one starts from x 0 = 2 and repeatedly applies f , one sees the sequence of values The cycle in this value sequence is 6, 3, 1 . Let S be any finite set, f be any function from S to itself, and x 0 be any element of S . For any i > 0 , let x i = f ( x i − 1 ) . Let μ be the smallest index such that

4686-453: The size of each value is Ω ( log ⁡ ( μ + λ ) ) {\displaystyle \Omega (\log(\mu +\lambda ))} . A number of authors have studied techniques for cycle detection that use more memory than Floyd's and Brent's methods, but detect cycles more quickly. In general these methods store several previously-computed sequence values, and test whether each new value equals one of

4757-494: The third occurrence of any value, i.e. the cycle will be iterated at most twice. This note also states that it is sufficient to store Θ ( log ⁡ λ ) {\displaystyle \Theta (\log \lambda )} previous values; however, the provided implementation stores Θ ( log ⁡ ( μ + λ ) ) {\displaystyle \Theta (\log(\mu +\lambda ))} values. For example, assume

4828-451: The time complexity of this algorithm is O ( ( μ + λ ) ⋅ log ⁡ ( μ + λ ) ) {\displaystyle O((\mu +\lambda )\cdot \log(\mu +\lambda ))} . Since it stores Θ ( log ⁡ ( μ + λ ) ) {\displaystyle \Theta (\log(\mu +\lambda ))} values, its space complexity

4899-490: The total number of vertices in the graph. The cycle double cover conjecture states that, for every bridgeless graph , there exists a multiset of simple cycles that covers each edge of the graph exactly twice. Proving that this is true (or finding a counterexample) remains an open problem. Several important classes of graphs can be defined by or characterized by their cycles. These include: Cycle detection In computer science , cycle detection or cycle finding

4970-515: The use of wait-for graphs to detect deadlocks in concurrent systems. The aforementioned use of depth-first search to find a cycle can be described as follows: where For undirected graphs, "neighbour" means all vertices connected to v , except for the one that recursively called DFS(v) . This omission prevents the algorithm from finding a trivial cycle of the form v → w → v ; these exist in every undirected graph with at least one edge. A variant using breadth-first search instead will find

5041-408: The value x μ reappears infinitely often within the sequence of values x i , and let λ (the loop length) be the smallest positive integer such that x μ = x λ + μ . The cycle detection problem is the task of finding λ and μ . One can view the same problem graph-theoretically , by constructing a functional graph (that is, a directed graph in which each vertex has

#87912