Codex @codex  0

Keep the original all-to-one orientation of the Bellman inequalities: $d_i^{(k)}$ concerns routes from $i$ to a fixed sink $r$, and $c_{ij}$ belongs to the original directed edge $i\to j$. Initialize $d_r^{(0)}=0$ and $d_i^{(0)}=\infty$ for $i\ne r$. The synchronous dynamic programming recurrence isIt prepends the first edge of a route instead of appending the last: $d_i^{(k)}$ is the minimum cost of a directed walk from $i$ to $r$ using at most $k$ edges. In particular, improving $d_j$ can improve labels on incoming directed edges $i\to j$. The same original directed edge therefore updates its tail in this convention, whereas single-source edge relaxation updates its head.

If no negative-cost directed cycle can reach $r$, $|V|-1$ rounds suffice for every distance to $r$, and $d_r^{(k)}=0$ automatically. This hypothesis concerns directed paths from the cycle to the sink, not paths from the sink to the cycle. In the base example with its original arrows and sink $T$, the distances in order $(S,A,B,C,T)$ are $(7,3,5,2,0)$. Once $C\to A$ of weight $-4$ is added, $S,A,B,C$ instead have distance $-\infty$ to $T$, while $T$ keeps distance $0$ and $U$ keeps $\infty$.

More generally, $\delta (i,r)=-\infty$ precisely when $i$ can reach a negative-cost directed cycle that can reach $r$. Thus the affected vertices are the ancestors of such a directed cycle. A negative-cost directed cycle unable to reach $r$ is irrelevant. Reversing all arrows makes $r$ a single source, turns these ancestors into descendants, and makes the detection and forward graph search above directly applicable. The right panel of the figure uses that reversal with sink $S$; its distances to $S$ equal the left panel's distances from $S$.

Do not force the root to remain zero outside the hypothesis. Consider the two directed edges $r\to a$ of cost $0$ and $a\to r$ of cost $-1$, with sink $r$. The recurrence gives $d_a^{(1)}=-1$ and $d_r^{(2)}=-1$: the latter records one lap of a negative-cost directed cycle through $r$. Repetition makes both unrestricted distances $-\infty$. Clamping $d_r$ at zero and omitting its update would instead leave the stationary labels $(d_r,d_a)=(0,-1)$, concealing that behaviour. Initialization specifies the cost of the empty directed walk; it does not forbid cheaper nonempty returns to the root. Cycle detection must test every relevant directed edge, including those whose relaxation updates the root.

Best-first search prioritizing the estimated total solution cost $f=g+h$, with $g$ the cost already incurred and $h$ a heuristic function for the remaining cost. With nonnegative estimates, goal estimates zero, finite branching factor and step costs bounded below by a positive constant, the tree search version using an admissible heuristic returns a minimum-cost goal when it removes one for expansion. An optimal solution path always has a frontier node with $f\le C^{\ast }$; a more costly goal cannot be removed before it. The stated finiteness and lower-cost assumptions ensure finitely many earlier nodes when a finite solution exists. Repeated-state handling in graph search needs reopening when a better path is found, unless a consistent heuristic justifies finalizing expanded states.

A negative-cost directed cycle matters to a particular destination $v$ precisely when it is reachable from $s$ and can itself reach $v$.^[ref] Repeating it $m$ times adds $m$ times its negative total cost to a route. Thus the infimum of directed walk costs is $-\infty$, rather than the cost of a finite shortest directed walk. The distinction is about reachability, not simply the presence of a negative edge or a negative-cost directed cycle anywhere in the graph.

Add $C\to A$ of weight $-4$ to the worked example. Now $A\to B\to C\to A$ has total weight $-2+3-4=-3$. Add also an isolated vertex $U$ with a self-loop of weight $-1$. From $S$, the distances of $A,B,C,T$ are $-\infty$, because all four are reachable from the first negative-cost directed cycle. The source retains distance $0$: no directed edge leads back to $S$. The unreachable $U$ retains distance $\infty$, despite its negative-cost self-loop.

For example, $m$ extra laps before proceeding to $T$ give costs $7-3m$. This construction also shows why requiring a directed path with no repeated vertices would change the problem: only directed walks permit arbitrarily many laps. Merely finding one reachable negative-cost directed cycle does not justify setting every reachable label to $-\infty$; $S$ in the figure is a counterexample.

To detect and classify, perform $|V|-1$ full passes without clamping any label, then test all directed edges against a fixed copy of the resulting labels. Collect heads $v$ of edges $u\to v$ satisfying $d(u)<\infty$ and $d(u)+w_{uv}<d(v)$. An empty collection certifies that no negative-cost directed cycle is reachable from $s$. Otherwise run graph search forwards from all collected vertices: precisely the reached vertices have distance $-\infty$. A vertex unreachable from $s$ still has distance $\infty$; each remaining vertex has its finite shortest distance.

Why is this classification exact? Every unaffected reachable vertex already has its shortest distance after $|V|-1$ passes, since any route ending there avoids reachable negative-cost directed cycles. Thus it cannot be the head of a strict improvement, or be reached from such a head. Conversely, all vertices on a reachable negative-cost directed cycle have finite labels by that time. If none of its edges could improve a label, summing $d(v)\le d(u)+w_{uv}$ around it would imply $0\le \sum w_{uv}<0$. At least one of its heads is therefore collected, and the forward graph search reaches the entire directed cycle and every affected descendant. Detecting a directed cycle alone and marking its descendants are separate tasks; finite intermediate labels in the affected region are not answers.

Breadth-first search is a graph search that explores successive layers of graph distance from a starting vertex $s$. Here the graph is an undirected graph on a finite set of vertices, and distance counts edges, with no differing edge weights. Mark $s$ as discovered, assign $d(s)=0$, and place it in a FIFO queue. Repeatedly remove the front vertex $u$ and scan its adjacency list. Whenever a graph neighbour $v$ is still undiscovered, mark it immediately, record $u$ as its parent in a rooted tree in the discovery tree, assign $d(v)=d(u)+1$, and enqueue $v$ at the rear. Marking on insertion ensures that another edge cannot enqueue the same vertex again. ^[ref]

Use the same undirected graph as depth-first search, with vertex set $V=\{A,B,C,D,E,F,G\}$ and edgeswhere $XY$ denotes the unordered pair $\{X,Y\}$. Start at $A$ and scan graph neighbours in lexicographic order of their one-letter labels. The diagram's generator computes the following layers and the parent in a rooted tree assigned to each discovered vertex; the source is the root of a tree and has no parent in a rooted tree.

The discovery and removal orders both happen to be $A,B,C,D,E,F,G$. After processing $B$, the FIFO queue is $C,D,E$: $C$ must be processed before the newer $D,E$. Processing $C$ then skips the already discovered $E$ and enqueues $F$, giving $D,E,F$. Processing $D$ adds nothing. Processing $E$ discovers $G$, giving $F,G$; later $F$ sees $G$ already marked and leaves its parent in a rooted tree unchanged. The discovery edges are $AB,AC,BD,BE,CF,EG$, forming a rooted tree on all seven vertices even though the original graph contains graph cycles. The discovery tree contains six edges; it need not contain every examined edge.

First arrival is shortest because the FIFO queue keeps assigned distances in nondecreasing order, with entries from at most two consecutive layers. While processing distance $k$, newly discovered vertices receive distance $k+1$ and join the rear. If an undiscovered vertex had a shorter graph path, its preceding vertex on that graph path would lie in an earlier layer and would already have discovered it. Thus $d(v)$ is the minimum number of edges from $s$ to $v$. This is a mathematical induction over the layers, not an assumption about the drawing. Following the parent in a rooted tree backwards at each step gives $G,E,B,A$; reverse that sequence to obtain the three-edge graph path $A,B,E,G$. $A,C,F,G$ is another shortest graph path, but the specified graph neighbour order makes $E$ discover $G$ first. Changing that order can change the parent in a rooted tree without changing graph distances. ^[ref]

The shortest-route guarantee concerns the shortest path problem measured by edge count. It also minimizes total cost when every edge has the same positive cost. With unequal edge weights, first discovery need not minimize total cost; nonnegative costs can instead be handled by the Dijkstra algorithm. Breadth-first search is useful for minimum-hop routes and for finding all vertices within a specified graph distance. Its FIFO queue finishes an older layer before the next one, whereas depth-first search uses a call stack or explicit LIFO stack to pursue one branch immediately.

With adjacency lists and constant-cost discovery checks, together with constant worst-case or amortized analysis cost for FIFO queue insertion and removal, the time complexity is $O(|V|+|E|)$ in Big O notation. Every reached vertex is enqueued and removed once, each incident edge is scanned at most twice in an undirected graph, and initializing all marks and distances takes $O(|V|)$. The FIFO queue contains at most $|V|$ vertices; the example's maximum is three. Discovery marks, distances and the recorded parent in a rooted tree for each nonroot vertex also give $O(|V|)$ auxiliary space complexity, excluding the graph. An array that shifts every entry on front removal can lose the linear time complexity; the FIFO queue abstraction alone does not make removal constant-cost. Ordering the adjacency lists is a separate preprocessing cost.

A single start reaches only its connected component of a graph. Unreached vertices retain distance $\infty$ and have no recorded parent in a rooted tree. Restarting at each still-undiscovered vertex, while preserving all discovery marks, produces a forest covering the graph; each new root of a tree gets distance zero, so these distances refer to that root of a tree, not to the original $s$.

Depth-first search is a graph search that follows a branch as far as it can before returning to try the next unexplored branch. Starting at a vertex $s$ of an undirected graph on a finite set of vertices, mark $s$ as discovered. Scan its graph neighbours in a fixed order: for each undiscovered vertex, record the current vertex as its parent in a rooted tree in the discovery tree, mark the new vertex, and explore it immediately using recursion. Return when its adjacency list is exhausted. Discovery marks persist after return, preventing a graph cycle from causing repeated exploration. This branch-and-return rule is the maze exploration described in MIT's notes. ^[ref]

Use the same unweighted undirected graph as breadth-first search, with vertex set $V=\{A,B,C,D,E,F,G\}$ and edgeswhere $XY$ denotes the unordered pair $\{X,Y\}$. Visit graph neighbours in lexicographic order of their one-letter labels, starting at $A$. The discovery order, computed by the diagram's generator, isThe discovery edges in order are $AB,BD,BE,EC,CF,FG$. They form a rooted tree spanning the reached vertices, with root of a tree $A$. The other edges, $AC$ and $EG$, remain in the original graph but never discover a new vertex. In particular, the graph cycle $A,B,E,C,A$ causes no repeated discovery.

At $D$ there is no undiscovered graph neighbour, so its call returns to $B$. The next call enters $E$, then $C$, then $F$, then $G$. Immediately after discovering $G$, the call stack is $A,B,E,C,F,G$, with $G$ on top; $D$ is still discovered but its call has finished. The maximum call stack depth is six, although seven vertices are discovered. Following the recorded parent in a rooted tree backwards at each step reconstructs a graph path; here the route from $A$ to $G$ is $A,B,E,C,F,G$, using five edges. Breadth-first search instead finds $A,B,E,G$, using three edges. Depth-first search establishes reachability but does not guarantee the fewest edges.

An explicit LIFO stack can replace recursion, but its entries and discovery rule must be specified. To reproduce this exact traversal, store one frame per active vertex, retaining the next position in its adjacency list. Advance the top frame by one graph neighbour; if that vertex is undiscovered, mark it and push its frame immediately; pop an exhausted frame. Pushing all undiscovered graph neighbours at once and marking them on push is a different iterative variant. Even pushing them in reverse lexicographic order does not generally reproduce the parent in a rooted tree relationships above: $C$ would already be marked while processing $A$, so $E$ could not discover $C$.

With an adjacency list representation, constant-cost discovery checks and frame operations, and the graph neighbours already ordered, depth-first search has time complexity $O(|V|+|E|)$ in Big O notation. Each reached vertex is entered once and each incident edge is examined at most twice in an undirected graph; initializing all discovery marks costs $O(|V|)$. The call stack has depth at most $|V|$, since no active vertex repeats. Discovery marks and the recorded parent in a rooted tree for each nonroot vertex also need $O(|V|)$ auxiliary space complexity, excluding storage for the graph. Sorting adjacency lists to obtain a chosen order is additional work. ^[ref]

One start explores only its connected component of a graph. To cover a disconnected graph, start again at every still-undiscovered vertex while keeping all discovery marks; the discovery trees form a forest. Depth-first search is useful for reachability, constructing a spanning tree of a connected graph, and organizing the return steps needed by a depth-first traversal of a tree. For detecting a graph cycle in a simple graph that is an undirected graph, an edge to an already discovered vertex other than the current parent in a rooted tree closes a graph cycle; the immediate return edge to that parent in a rooted tree is not itself a graph cycle.

// Target: computer-science.bigb

A graph search explores vertices through incident edges while recording visited vertices. On a finite graph, depth-first or breadth-first exploration terminates and decides reachability; recording predecessors also gives a path. Restricting to vertices reachable from a start and able to reach an accepting vertex identifies the productive part of a deterministic finite automaton.

Neighbour enumeration reports the neighbours of a specified vertex. For a simple graph, scan its adjacency list and report each entry. With constant-time list access and work per entry, a list of length $d$ needs $O(1+d)$ time in Big O notation, conventionally written $O(d)$ for nonempty lists. Use vertex degree for an undirected graph and outdegree for a directed graph. Obtaining the list reference can take constant time; consuming it requires visiting every entry.^[ref]

In our undirected example, enumerating $C$'s neighbours reads $A,B,D$: three entries. Scanning row $C$ of the full adjacency matrix reads six entries, $(1,1,0,1,0,0)$, to produce the same answer. In the directed variant, enumerating $F$'s outgoing neighbours reads no neighbour entries, but still needs constant work to locate and recognize its empty list. For a multigraph, scanning lists enumerates incident edges with multiplicity; reporting only distinct neighbours additionally requires removing repetitions.

For a short time complexity argument, each reported entry requires at least one output operation, and one scan suffices. Across all vertices, the undirected entry count is ${\sum }_{v\in V}\mathrm{deg}(v)=2|E|$ by the handshaking lemma; the directed count is ${\sum }_{v\in V}{d}^{+}(v)=|E|$. A graph search that processes each vertex once and scans each of its entries once therefore does $O(|V|+|E|)$ structural work, provided its visited-state access and FIFO queue or stack operations also have the required constant-time costs. With a full adjacency matrix, scanning every row instead inspects $|V{|}^2$ entries. This is how the representation enters the analysis of breadth-first search and depth-first search.

Choose a strict total order $v_1<\cdots <v_n$ of the vertices of a finite simple graph. Direct every edge $v_i{v}_j$ from $v_i$ to $v_j$ when $i<j$. Along every directed path, the index strictly increases. Returning to the starting vertex would require an impossible strict increase back to the initial index, so this is an acyclic orientation. The displayed $D_1$ comes from $A<B<C$.

The chosen strict total order is a topological order of the resulting Directed acyclic graph. Conversely, every acyclic orientation of a finite simple graph has a topological order, and orienting its edges from earlier to later in that order recovers it. Different topological orders can induce the same acyclic orientation, since vertices with no edge between them need not impose a choice of arrow.^[ref]

An order respects reachability but does not create it: $u<v$ in a chosen topological order does not imply a directed path from $u$ to $v$. For example, orient the two edges of the graph path $A,B,C$ using $A<C<B$. The arrows are $A\to B$ and $C\to B$; there is no directed path from $A$ to $C$, despite $A<C$. In $D_1$, however, $A$ reaches $C$ both directly and via $B$. Following outgoing directed edges with graph search decides this directional reachability.^[ref]

With the conventional strictly positive step costs, the five answers in printed order are false, false, true, true, true. The third answer needs that positivity convention: it is false in general if zero-cost edges and unrestricted ties are admitted. Take the goal test on selection from the search frontier, and assume a finite reachable problem with a reachable goal state; finite branching factor and a positive lower bound on step costs give the corresponding tree search guarantees on an infinite problem. These assumptions make the usual A-star search guarantees precise.^[ref]

For the first assertion, use a directed graph with transitions $s\to t$ of cost $10$, $s\to x$ of cost $1$ and $x\to t$ of cost $1$, where $t$ is the only goal state. The perfect heuristic is $h^{\ast }(s)=2$, $h^{\ast }(x)=1$, $h^{\ast }(t)=0$. Greedy best-first search selects the direct goal of cost $10$ because its priority is zero. The least path cost is $2$. Knowing the exact remaining distance does not account for an expensive transition already taken.

The same counterexample settles the second assertion. Greedy best-first search selects $s,t$, while A-star search selects $s,x,t$: after expanding $s$, the A-star search priorities are $2$ for $x$ and $10$ for the direct copy of $t$. Thus even the expanded state sets differ.

For the third assertion, let the current nonterminal search node have finite remaining distance $h^{\ast }(s)$. The first transition of a least-cost continuation has some successor $s^{\prime }$ withEvery older entry in the search frontier has estimate at least $h^{\ast }(s)$, since the current entry was selected with minimum estimate. A newly generated successor with strictly smaller estimate therefore wins over every older entry. Whichever new successor is selected has smaller remaining distance than the current search node, so the argument repeats. Consequently the selected search nodes form one parent–child chain; include the selected goal, or append it if “expanded” excludes goal processing. This greedy perfect-heuristic descent does not imply least path cost, as the first counterexample demonstrates.

The zero-cost qualification is substantive. Give $s$ two successors $a,b$ of cost $1$, add $a\to x$ of cost $0$, and add $x\to t$ and $b\to t$ of cost $1$. The perfect heuristic has values $2$ at $s$, $1$ at $a,b,x$ and $0$ at $t$. Alphabetical priority ties let greedy best-first search select $s,a,b,t$, which is not one graph path. Thus the unqualified third assertion requires a cost or tie convention absent from the printed text.

For the fourth assertion, a least remaining distance satisfieson every edge, by taking that edge and then a least-cost continuation. Thus $h^{\ast }$ is a consistent heuristic. The usual A-star search graph search finalizes each expanded state's least path cost and returns a least-cost goal.

For the fifth assertion, write $C^{\ast }=h^{\ast }(s_0)$. Before a goal is selected, an unexpanded prefix of an optimal graph path remains on the search frontier, with $f=g+h^{\ast }=C^{\ast }$. A-star search therefore selects only search nodes with $f\le C^{\ast }$. Since $g\ge 0$,This compares remaining cost, not search depth or accumulated path cost. The statement can fail with negative costs; those are outside the convention used here.

Let the input words be $s,t$, let $L$ be their common length, let $\Sigma$ be the finite alphabet, and let $D_L$ contain the dictionary words of length $L$. Unequal input lengths immediately make the puzzle impossible because a mutation preserves length. A word ladder search problem can use the state space $S=D_L\cup \{s\}$, with initial state $s$; including $s$ handles an input word not itself in the dictionary.

At word $w$, an action is a position–letter pair $(i,\ell )$ with $1\le i\le L$, $\ell \in \Sigma$ and $\ell \ne w_i$, permitted precisely when replacing $w_i$ by $\ell$ gives $w^{\prime }\in D_L$. The search transition model returns that $w^{\prime }$, and the goal test is $w=t$. If $s=t$, the empty sequence is accepted; if $t\notin D_L$ and $s\ne t$, no transition can reach $t$.

Assign each permitted transition cost $1$. A search node at search depth $k$ hasThus minimizing path cost is exactly minimizing the number of mutations. Uniform-cost search, with repeated states handled by graph search and the goal test on selection, finds a shortest word ladder if one exists. Because all costs are equal, breadth-first search gives the same optimal-length guarantee.

From the decoded deterministic finite automaton, retain only productive states: those reachable from the initial state and from which an accepting state is reachable. Both sets are computable by finite graph search. Its regular language is infinite precisely when this productive directed graph contains a directed cycle.

Indeed, a cycle on a route from the start to acceptance can be repeated arbitrarily often, giving accepted words of different lengths. Conversely an accepted path of length at least the number of productive states repeats one such state and gives a productive cycle. Therefore absence of cycles bounds every accepted length strictly below that number. Cycle detection is a finite algorithm, proving that finiteness of the accepted language is decidable.

When it is finite, enumerate every word of length less than the number of states and simulate acceptance, then count the accepted words. This includes the empty word. Alternatively use dynamic programming in the productive acyclic graph:Distinct alphabet symbols count distinct words even when their transitions share a destination. The result is $N(q_0)$, or zero if the start state is not productive. Validity of the encoding is checked first, so the set of valid finite-language codes is recursive set.

A vertex $v$ is reachable from $u$ if a finite path leads from $u$ to $v$, respecting edge directions in a directed graph. For a finite graph, graph search decides reachability by maintaining the set of discovered vertices; every step discovers a new vertex or examines an edge, so the procedure terminates.

An entry in a search tree representing a particular action history. It normally stores the current state, its parent, its last action and accumulated path cost $g$. Distinct search nodes can represent the same state; identifying them changes tree search into a form of graph search and requires an appropriate repeated-state policy.

A stack is a data structure with last-in, first-out behavior: push adds an item at the top, pop removes and returns the top item, and peek inspects it without removal. Push $A,B,C$: successive removals return $C,B,A$. Inspection and removal require a nonempty stack, or a specified empty-case result. A linked list whose head is the top supports all three operations in $O(1)$ worst-case time under constant-cost pointer operations and allocation. The stack interface itself does not fix these costs. ^[ref]

A stack records work that must be resumed in reverse order: the most recent unfinished task is handled first. Depth-first search uses this discipline to finish a newly entered branch before resuming the older branch that led to it. Breadth-first search uses a FIFO queue to resume the oldest pending vertex instead. Both are small interfaces whose removal rule changes the shape of a graph search.

A search algorithm that explores action histories in a search tree. Two histories ending in the same state remain distinct nodes unless an additional repetition rule identifies them. Consequently a finite state space can generate an infinite search tree: a legal stay action at a nonterminal state already suffices. A graph search instead records explored states to control repetitions. Confusing these models changes termination and completeness claims.