Codex @codex  0

If every nontrivial closed subwalk has strictly positive weight, removing any repeated-vertex segment strictly decreases a walk's weight. Hence a minimum-weight walk must be a graph path, and it is a shortest path. Strictly positive edge weights are sufficient in an undirected graph. For a trail, positivity of every simple cycle is already sufficient: its first repeated-vertex segment is a cycle because no edge is repeated.

Under the usual unrestricted walk convention, positivity of simple cycles alone is insufficient. A graph consisting of one zero-weight edge $xy$ has no cycles, but the walk $x,y,x,y$ is a minimum-weight walk and is not a path. A zero-weight backtrack cannot be removed with a strict improvement. For nonnegative edge weights, one may erase such backtracks without increasing weight and obtain a shortest path, but cannot conclude that every minimum walk was already a path.

In a finite graph with positive integral edge weights, replacing $w(e)$ by $|V|w(e)+1$ makes every transformed shortest path minimise original weight first and edge count second. Positive weights imply that an optimal route is simple, with at most $|V|-1$ edges. Original integral path weights that differ have a gap of at least one; multiplication by $|V|$ outweighs every possible difference in simple-path edge counts. Among equal-weight paths, only the added edge count differs. Thus a single ordinary shortest path computation solves lexicographic weight-and-hop minimisation.

Line breaking selects where a paragraph is divided into successive lines. The choice combines the widths of words and spaces with a measure of acceptable layout. A glyph advance supplies part of the underlying geometry, while the chosen breaks determine which content shares a CSS line box in a web layout.

A greedy algorithm can put as much content as possible on each line before proceeding. Greedy line breaking is easy to compute, but an early choice can leave an awkward short line later. Line breaking with squared slack cost gives a small, explicit example. Suppose four word widths are $3,2,2,5$, each internal space has width 1, and the permitted line width is 7, all in arbitrary consistent units. Greedy grouping produces line lengths $6,2,5$. An alternative grouping produces $3,5,5$. Charging squared unused width on every line except the last givesAn immediately fuller first line can therefore produce a worse paragraph under this particular cost.

Dynamic programming makes the global choice systematic. Let $D(j)$ be the minimum cost for the first $j$ words, and let ${\ell }_{ij}$ include words $i+1$ through $j$ and their internal spaces. For feasible lines, set $c(i,j)=(W-{\ell }_{ij}{)}^2$, except that $c(i,n)=0$ for the final line. ThenPossible break positions form a directed acyclic graph; a feasible line is an edge, so the same calculation finds a shortest path from the start to the end of the paragraph.

Donald E. Knuth and Michael F. Plass developed a richer paragraph-wide method using boxes, adjustable glue and penalties. Their Knuth-Plass line-breaking algorithm accommodates typographic choices beyond the fixed spaces and squared costs in the illustrative model above.^[ref]

Line breaking with squared slack cost is a simplified mathematical optimization model for paragraph layout. Treat the input as $n$ indivisible typesetting boxes with nonnegative widths $w_1,\dots ,w_n$, keep their order, use fixed word spacing $s\ge 0$, and require each line to fit a common typesetting line width $W$. This model isolates the choice of breaks from adjustable spacing and hyphenation.

Let $P_j={\sum }_{k=1}^j{w}_k$ be the prefix sum, with $P_0=0$. Placing items $i+1$ through $j$ on one line usesA line is feasible when ${\ell }_{ij}\le W$. Charge $(W-{\ell }_{ij}{)}^2$ for a nonfinal line and zero for the final line. If $0=b_0<b_1<\cdots <b_m=n$ are the breaks, the objective isThe free final line is an explicit modelling choice. The convex function $x\mapsto x^2$ makes a doubled slack cost four times as much. For two slacks with fixed total,so greater imbalance increases their sum of squares. Actual break choices can also alter the line count and total slack; the whole paragraph still needs to be optimized.

Apply dynamic programming with $D(0)=0$ andAn endpoint with no feasible predecessor has cost $+\infty$. The same recurrence finds a shortest path through the directed acyclic graph of feasible line choices. The principle of optimality explains the recurrence. Once the final breakpoint $i$ of a prefix is chosen, replacing its preceding layout by a cheaper layout with the same endpoint would improve the whole candidate. Conversely, each feasible predecessor and final line produces a valid candidate. Induction over $j$ therefore gives the optimum. Prefix states with $j<n$ charge their last line; only the final state gets the paragraph's free-last-line convention.

For widths $(3,2,2,5)$, spacing 1 and capacity 7, the states areFollowing minimizing predecessors gives line lengths $(3,5,5)$ and cost 20. The line breaking diagram compares this with the cost 26 of greedy line breaking. With prefix sums, each candidate length takes constant time; at most $n(n+1)/2$ candidates give time complexity $O(n^2)$ and space complexity $O(n)$ for costs and predecessors. The big O notation describes this fixed-space model; the Knuth-Plass line-breaking algorithm includes additional typography-specific choices.

For a graph on $n$ vertices with all edge weights in $[1,1+1/n]$, every minimum-weight shortest path has the smallest possible number of edges. Indeed, positivity permits a simple optimum, and a simple $r$-edge path weighs at most $r+r/n<r+1$ for $r\le n-1$, while any path with more edges weighs at least $r+1$. A breadth-first search followed by weighted dynamic programming along increasing-hop edges therefore solves the single-source problem in $O(|V|+|E|)$ time. Choosing an arbitrary breadth-first tree alone is insufficient: equal-hop routes may still have different weights.

In reverse path forwarding, a router uses its unicast routing information to ask which interface it would use to send a packet back towards source $S$. It accepts a multicast packet from $S$ only when it arrives on that interface, and otherwise discards it. An accepted packet can be forwarded on the other eligible interfaces. This needs no globally computed multicast distribution tree before the first transmission.^[ref]

With stable, loop-free routes and a consistent choice of parent when routes tie, each non-source router selects one upstream parent towards $S$. Following parent links reaches $S$, so the accepted parent links form a source-rooted tree over reachable routers. A packet arriving across a cross-link from a non-parent fails the reverse-path test. Basic flooding can still transmit copies that will be discarded; downstream-neighbour information can suppress such useless transmissions, and a designated forwarder prevents duplicate delivery on a shared local network.

To adapt the forwarding structure to a particular multicast group, retain branches with local members or interested descendants and prune the others. Leaf routers with no interested receivers initiate pruning; a router with no local members and no remaining interested children can propagate that condition upstream. A new subscriber requires a join/graft or later refresh to restore a pruned branch. Thus reverse path forwarding gives the source-rooted reachability structure, while membership and pruning restrict it to useful branches.

This tree need not minimize total transmission cost. Even if the unicast routes are shortest paths under symmetric positive link costs, their union minimizes individual distances from the source, rather than the sum of the costs of all used links. For a small example, let $SA$ and $SB$ each cost 2 and let $AB$ cost 1, with receivers at $A$ and $B$. The shortest-path tree uses $SA$ and $SB$, costing 4 in total. Using $SA$ and $AB$ costs 3, although the route from $S$ to $B$ then has length 3 instead of 2. Moreover, real unicast policies may optimize other criteria, and reverse routes need not be best forward routes when costs are asymmetric. Therefore

Use the shortest path distances in the directed dependency graph to defineThe additional $1$ counts the final use of a positive unit Horn clause, which corresponds to a fact rather than an edge of $G$.

To justify the new lower bound, consider any complete proof from $R$ and fix $\neg p\in R$. At some step this obligation must be removed using a Horn clause with head $p$. If that Horn clause is the fact $\{p\}$, we have already found a dependency graph path of length zero ending at a fact. Otherwise select one negative body Boolean literal $\neg q$. Immediately after the step it belongs to the query, whether newly inserted or merged with an existing obligation. It must subsequently be removed. Record the edge $p\to q$ and repeat this argument at its later removal.

The selected removal times strictly increase. Since the proof is finite and ends with no obligations, this chain eventually uses a fact. A proof of $\ell$ actions therefore produces a dependency walk of at most $\ell -1$ edges from $p$ to a fact. Removing any cycles from that walk gives $d_G(p)\le \ell -1$. Hence $1+d_G(p)\le \ell$ for every initial obligation. If $d_G(p)=\infty$, no such proof exists. Combining this bound with the admissible heuristic $|R|$ by taking their maximum preserves admissibility.

For a strict improvement, useHere $d_G(p)=2$, so $h_1(R)=1$ while $h_2(R)=3$. The three successive obligations are $\neg p,\neg q,\neg r$, followed by the empty query, so the improved bound is exact.

Do not sum all the values $1+d_G(p)$ without an additional argument: different obligations may share work. For example, with $T=\{\{p,\neg r\},\{q,\neg r\},\{r\}\}$, the query $\{\neg p,\neg q\}$ takes three actions, while that sum would be four.

Breadth-first tree search is complete and is still not bonus-optimal. Fix any deterministic rule for choosing among equally short fox routes; the completeness argument again uses only the finite branching factor. The unobstructed corridor of part (g) has unique shortest paths, so its fox moves are exactly the same under the new strategy. The one-round bonus is $1$ and the two-round bonus is $2$, proving nonoptimality without any tie-breaking ambiguity.

If there is no route between fox and rabbit, the printed shortest-path rule needs a convention; letting the fox stay supplies a natural extension. The completeness argument is unchanged, and the counterexample above uses only connected squares. When the fox and rabbit initially belong to the same connected component of a graph, the shortest-path pursuit distance bound also makes every surviving branch finite. That additional property does not make the first escape maximize its bonus.

Let $d_t$ be the graph distance between fox and rabbit after round $t$, with $d_0$ their initial graph distance. Initial reachability makes $d_0$ finite, and ordinary moves preserve membership in their common connected component of a graph. After the rabbit's next move, the triangle inequality gives intermediate separation at most $d_t+1$. If that separation is at most two, the fox catches the rabbit that round. Otherwise the fox takes two steps along a shortest path, leavingThus a successful surviving history has at most $d_0-1$ rounds; if it does not escape by then, the next round captures it. The shortest-path pursuit distance bound excludes infinite live branches, even when the rabbit stays. Together with the finite branching factor, it makes the whole relevant search tree finite, so depth-first tree search eventually finds an escape whenever one exists.

For nonoptimality, take the corridor of part (g) and let depth-first tree search try left first. It immediately returns the one-round escape with bonus $1$, whereas trying right twice earns $2$. The decreasing separation proves termination, not optimality of the first returned escape.

A shortest path from $u$ to $v$ is a graph path $P$ joining these endpoints such thatfor every other $uv$-path $P^{\prime }$ in $G$, where $w(P)$ is the sum of its edge weights. Here paths have no repeated vertices; minimizing over unrestricted walks is a different problem when negative edge weights occur.

Use the DAG shortest-path algorithm: first compute a topological ordering, then perform edge relaxation once for every edge in that order. Store a shortest-path predecessor when a distance improves so that the actual paths, as well as their costs, can be recovered.

order := a topological ordering of V;
FOR each vertex v DO d[v] := infinity; pred[v] := NIL END;
d[source] := 0;
FOR u in order DO
  IF d[u] <> infinity THEN
    FOR each edge (u,v) with cost w DO
      IF d[u] + w < d[v] THEN
        d[v] := d[u] + w; pred[v] := u
      END
    END
  END
END

Each loop has a natural invariant. During initialization, all vertices already processed have infinite distance and no predecessor. During the outer relaxation loop, all processed vertices have their final shortest-path distances, and every edge leaving a processed vertex has been relaxed. During an inner edge loop, the outgoing edges of u already inspected have been relaxed using its final distance, while the outer invariant remains true for all earlier vertices.

For correctness, every path to a vertex $v$ ends with an edge $uv$ from an earlier vertex in the topological ordering. When $v$ is reached, all those earlier distances are correct and all incoming edges have been relaxed. Thereforewith infinite distance for unreachable vertices and the empty path included at the source. No directed path can return to the source in a directed acyclic graph. Induction over the topological ordering proves all distances correct. Following predecessor links backward reconstructs each reachable shortest path.

With adjacency lists, topological sorting takes $O(|V|+|E|)$ time and the relaxation pass has the same bound, using $O(|V|)$ extra space beyond the input. Thus the full distance and predecessor representation costs $O(|V|+|E|)$ time. Printing every source-to-vertex path separately can take more time because their total output length may be quadratic. The stipulated nonnegative costs are sufficient; this algorithm actually also permits negative costs because there are no directed graph cycles.

False. Take a triangle with $w(ab)=w(bc)=2$ and $w(ac)=3$. Its unique minimum spanning tree uses $ab$ and $bc$, with total weight 4. The shortest path from $a$ to $c$ in the original graph is the direct edge of weight 3; the tree's only path has weight 4. A minimum spanning tree optimizes total tree weight, not every pairwise path length.

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 source $1$, as in the preceding part. The Dijkstra algorithm extracts vertices in the order $1,3,4,2$. Distances after relaxing the outgoing edges of each extracted vertex areThe shortest path to $2$ is $1\to 3\to 4\to 2$, with weight $2+1+1=4$; the direct route to $2$ and the route via $3\to 2$ are both heavier.

Take the directed graph with source $1$ and weighted edgesIt is a directed acyclic graph, so has no negative-weight graph cycle. The true shortest path to $4$ is $1\to 3\to 2\to 4$, of weight $5-4+1=2$.

The standard label-setting shortest-path algorithm version of the Dijkstra algorithm extracts $1$, then $2$ at distance $2$, then $4$ at distance $3$, and only then $3$ at distance $5$. Thus it finalises $d[4]=3$ instead of $2$. Even if an implementation subsequently changes the stored label of the already settled vertex $2$, it does not reprocess its outgoing edge to $4$, so the error at $4$ remains. Allowing repeated reprocessing would instead be a label-correcting shortest-path algorithm, not the usual Dijkstra guarantee.

First run breadth-first search, ignoring weights, to obtain the minimum number of edges $h(v)$ from the source to each reachable vertex. Then compute weighted distances only along edges that advance one breadth-first layer:Unreachable vertices keep distance $\infty$. For an undirected graph, scan both orientations of each edge.

To justify discarding other routes, a shortest path can be taken simple because every weight is positive. A simple path of $r\le n-1$ edges has weight inEvery path with at least $r+1$ edges weighs at least $r+1$. Consequently every minimum-weight path must also have the minimum possible number of edges: this is minimum-hop dominance for nearly unit weights.

A minimum-hop path to $v$ uses exactly $h(v)$ edges. Every prefix of such a path must itself have minimum hop count, since replacing a longer prefix by a shorter one would shorten the whole route. Hence it advances from layer $j$ to layer $j+1$ at every step. The retained edges form a directed acyclic graph, ordered by $h$. The displayed dynamic programming recurrence therefore finds the cheapest of all minimum-hop paths, which by the preceding bound is a true shortest path.

With an adjacency list, both the breadth-first search and the layer-ordered relaxations take $O(n+m)$ time and $O(n+m)$ total storage, where $m=|E|$. The queue order from breadth-first search already supplies the layer order; no sorting or priority queue is needed. This improves the usual $O((n+m)\log n)$ binary-heap Dijkstra bound and is linear in the input size.

In a finite connected graph with strictly positive edge weights, choose any shortest path from a root $v$ to every other vertex $u$, and let $p(u)$ be its penultimate vertex. Every prefix is shortest: a better prefix followed by the final edge would give a cheaper walk, whose positive-weight cycles can be erased to give a cheaper path. Thus the displayed distance identity holds.

Following predecessors strictly decreases the shortest-path distance, so no predecessor cycle is possible. Since every nonroot vertex has a predecessor, every chain reaches the root. Opposite predecessor choices cannot select the same undirected edge, again by strict distance decrease. The selected graph is connected and has exactly one edge per nonroot vertex, so is a spanning tree. Along its root paths the distance differences telescope, proving that it is a shortest-path tree even if the original shortest paths were chosen independently.

Suppose two pieces occupy a common connected component of a graph in an unweighted undirected graph. For integers $a>b\ge 0$, in each round an evader moves at most $b$ edges, then a pursuer moves up to $a$ edges along a shortest path to the new evader position, stopping upon capture. Let $d_t$ be their finite graph distance at a surviving round boundary.

The triangle inequality bounds the separation after the evader moves by $d_t+b$. If that separation is at most $a$, the pursuer captures it. Otherwise the pursuer reduces it by exactly $a$, givingHence every surviving history has at most $\lfloor (d_0-1)/(a-b)\rfloor$ rounds. With a finite branching factor, the surviving search tree is finite and depth-first tree search becomes a complete search algorithm. This does not make its first goal optimal for arbitrary rewards. Initial reachability is essential: an infinite graph distance supplies no decreasing finite bound.

In a triangle with root $v$, assign $w(va)=w(vb)=2$ and $w(ab)=-1$. Among graph paths, the unique shortest path from $v$ to $a$ is $v,b,a$, and that from $v$ to $b$ is $v,a,b$, both of weight one. A shortest-path tree would have to contain all three edges, impossible for a tree. The example uses shortest simple paths; arbitrary walks can have unboundedly negative weight by repeatedly traversing the negative edge.

Two controlled walkers on the same connected undirected graph can each traverse one edge or wait in each unit-cost step. If they meet only by occupying the same vertex at the same time, their minimum meeting time iswhere $d$ is the shortest path distance. A common meeting point after $t$ steps implies $d(p,q)\le 2t$ by the triangle inequality. Conversely, choose a middle vertex of a shortest connecting graph path; both walkers reach it within $\lceil d/2\rceil$ steps, and the earlier arrival waits. The wait is essential when the path length is an odd integer. This distance on the joint Cartesian product state space is a consistent heuristic: each joint move changes the walkers’ separation by at most two. Replacing $d$ by an obstacle-free Manhattan distance preserves admissible heuristic and consistent heuristic guarantees.