For a positive remaining fraction $n/d$, the condition $1/q\le n/d$ is equivalent to $q\ge d/n$. Since $1/q$ decreases as the positive integer $q$ increases, choose $q=\lceil d/n\rceil$. The zero fraction needs no term. This is the greedy Egyptian fraction expansion.

The remaining fraction isThe defining inequalities $q-1<d/n\le q$ give $0\le nq-d<n$. Therefore the unreduced new numerator is a nonnegative integer strictly smaller than the old positive numerator. Passing to a reduced fraction can only reduce it further. That numerator is a loop variant, so the process terminates. The increasing denominators are not the termination argument; their size need not be bounded in advance.

Use the remainder form of the Euclidean algorithm to compute the greatest common divisor, then divide both components of the fraction by it:The loop invariant is $a>0$, $b\ge 0$, and $\gcd (a,b)=\gcd (den,num)$. Initially it holds by symmetry of the greatest common divisor. For $b>0$, the integer division identity $a=qb+r$, with $0\le r<b$, shows that $a,b$ and $b,r$ have exactly the same common integer divisors. Thus the update preserves the loop invariant. The loop variant is the nonnegative integer $b$, which strictly decreases on each iteration. At exit $b=0$, so $a=\gcd (den,num)>0$. Dividing by $a$ preserves the rational number and makes the returned components coprime. In particular, zero is returned as $(0,1)$. No multiplication is needed, and all remainders remain within the original nonnegative Int range.

All edge lengths are positive, so run the Dijkstra algorithm from every source $s$, retaining distances $d_s$ and a shortest-path tree of its reachable component. Each run takes $O((|V|+|E|)\log (|V|+1))$ with a binary heap. The following scans after each run use only $O(|E|)$ additional work.

For a directed graph, inspect every closing edge $(u,s)$ and consider $d_s(u)+w(u,s)$ when $u$ is reachable. The tree route from $s$ to $u$ followed by this edge is a closed walk. Every directed cycle supplies one such upper bound by choosing any of its vertices as $s$; the shortest route to its predecessor is no longer than the corresponding cycle segment. Positivity lets any repeated portion be removed, so the smallest candidate is the shortest directed-cycle length.

For an undirected graph, do not combine an edge with the distance between its endpoints indiscriminately: that can count traversal of one bridge out and back as a false cycle. Instead inspect only edges $\{u,v\}$ absent from the current shortest-path tree, with both endpoints reachable, and considerThe two tree routes and this non-tree edge contain a genuine cycle. If they share a prefix, its cost is counted twice, so that cycle is no longer than the candidate. Every candidate is consequently at least the global shortest-cycle length.

To prove equality is attained, take a shortest cycle $C$ and a source $s$ on it. If either cycle edge incident to $s$ is absent from the tree, its candidate uses a shortest route no longer than the rest of $C$, so it is at most the length of $C$. Otherwise both incident edges are in the tree, and their other endpoints lie in different branches below $s$. Along the remaining segment of $C$, some edge crosses between different branches. Such an edge is not a tree edge. The two distances to its endpoints are bounded by the two corresponding, disjoint segments of $C$ from $s$; their sum plus the crossing edge is at most the length of $C$. Thus some candidate is no greater than the optimum, completing the proof.

Return the smallest finite candidate, or report acyclicity if none exists. The total running time is $O((|V{|}^2+|V||E|)\log (|V|+1))$, as required. The ordinary convention is a simple graph; if parallel edges are allowed, track actual edge identities when excluding tree edges, and treat a self-loop as its own cycle rather than discarding it. This is shortest cycle by repeated shortest-path trees.

Initialize $d[s]=0$ and $d[v]=\infty$ elsewhere. Perform $|V|-1$ full passes over the directed edges, applying edge relaxation $d[v]\leftarrow \min \{d[v],d[u]+w(u,v)\}$ whenever $d[u]$ is finite. For an undirected graph, process each edge in both directions. Stop early if a pass makes no change.

Each finite label records the cost of a discovered directed walk, so it never understates the true infimum. After $t$ passes, relaxation has propagated along every route of at most $t$ edges, so the label is no greater than the cost of any such route. If no reachable negative-cost closed walk exists, an optimal route can be chosen without repeated vertices and has at most $|V|-1$ edges. These inequalities prove that the final labels are the desired shortest path lengths.

An additional pass checks for an improving edge from a reachable vertex. If one exists, report a reachable negative-cost cycle: finite shortest distances cannot be assigned to vertices reachable from that cycle. Mark those vertices by forward reachability if individual $-\infty$ answers are wanted. In particular, a reachable negative undirected edge becomes a negative two-arc closed walk under the bidirected interpretation; generic signed weights do not guarantee finite answers.

Each pass costs $O(|E|)$, giving $O(|V||E|)$ for the usual Bellman-Ford algorithm bound. Including initialization gives $O(|V|+|V||E|)$, which also handles an edgeless graph honestly; these coincide in order when $|E|\ge 1$.

Use unit-cost insertion, deletion and substitution of one symbol. Their minimum total cost is the edit distance. Let $D[i,j]$ be the edit distance between the first $i$ symbols of the first sequence and the first $j$ of the second. Initialize $D[i,0]=i$ and $D[0,j]=j$. For $i,j>0$ computeThe cases delete the final source symbol, insert the final target symbol, or align the two final symbols, paying one for substitution and zero for a match. Every optimal alignment ends in one of these cases, and each case extends a valid shorter alignment. Induction on $i+j$ proves the dynamic programming recurrence correct.

Fill rows or columns in increasing order so every dependency is already available. There are $(m+1)(n+1)$ entries with constant work per interior entry: $O(mn)$ running time for nonempty sequences, or $O((m+1)(n+1))$ including the boundary cases. The full table has space complexity $O(mn)$; two rows give $O(n)$ auxiliary space when only the distance is wanted. Predecessor choices in the full table recover an optimal edit sequence.

Given the target's current heap index $i$, remove it as follows. If $i=n$, discard the last entry. Otherwise replace $A[i]$ by $A[n]$ and reduce $n$ by one. If the replacement is larger than its parent in a rooted tree, use sift up; otherwise use the maximum-oriented sift down from $i$.

Only comparisons incident to the replacement can initially violate the heap order. If it exceeds its parent, it also dominates the old children because the old key dominated those children and was no larger than the parent; an upward repair suffices. Otherwise the upward comparison is valid and only a downward repair can be needed. Thus removal takes $O(\log n)$ worst-case time after the location is known. Searching an unindexed heap for an arbitrary specified key can instead require $\Theta (n)$ time; the logarithmic bound does not include such a search.

A maximum priority queue stores keyed entries and supports insertion, inspection and removal of an entry with greatest key, and key increases. A max-heap gives the following running times, with the size/capacity cost of the backing array accounted for separately:

Empty-queue inspections and removals need an explicit failure result. The index argument to increaseKey must identify the entry's current location: if callers use item handles, update their location records during swaps.