Codex @codex  0

Compute a minimum spanning tree, then a minimum-weight perfect matching on its odd-degree vertices. Their multiset union is connected with even degrees, so it has an Euler circuit. Shortcut repeated vertices to obtain a metric tour. The tree costs at most the optimal tour, and shortcutting the optimal tour to its odd-degree subset gives a cyclic order whose alternating matchings show that the added matching costs at most half the optimum. The result is a polynomial-time $3/2$-approximation algorithm for symmetric metric instances.

The Dijkstra algorithm solves the single-source shortest path problem in a finite graph with nonnegative edge weights, finding distances to all reachable vertices. Start with tentative distance $d(A)=0$ and $d(v)=\infty$ elsewhere. Repeatedly choose the unfinalized vertex with least tentative distance, declare that label permanent, and perform edge relaxation on its outgoing edges. For an undirected graph, inspect both directions. A finite tentative distance always records the cost of a discovered graph path, but can improve before finalization.

In our example, finalizing $A$ discovers $C$ at $1$, $B$ at $4$, and $D$ at $10$. Choose $C$ next: edge relaxation through $C$ lowers $B$ to $1+2=3$ and $D$ to $1+5=6$. Choose $B$: edge relaxation through $B$ lowers $D$ to $3+1=4$. Finally choose $D$. The permanent distances are therefore $A:0$, $C:1$, $B:3$, $D:4$; the evolving tentative distances were $B:4\to 3$ and $D:10\to 6\to 4$.

Store a shortest-path predecessor whenever edge relaxation improves a label. The final table contains enough information to reconstruct routes, rather than merely their costs:

Following shortest-path predecessors backwards gives $D,B,C,A$; reversing the order gives $A,C,B,D$. If only this destination matters, stop when $D$ is finalized. Stopping when $D$ is first discovered would incorrectly return $10$. If the smallest remaining tentative distance is $\infty$, all remaining vertices are unreachable.

Why is the permanent choice safe? Suppose the selected vertex $u$ had a cheaper graph path. Let $y$ be the first unfinalized vertex on that graph path. Its preceding vertex was finalized, so edge relaxation has already offered $y$ a label no larger than that prefix's cost. Nonnegative remaining edge weights make the whole cost at least this prefix's cost; selection gives $d(u)\le d(y)$. A cheaper graph path would contradict these comparisons. Zero weights are allowed; ties can be resolved arbitrarily. This is the reason the label-setting shortest-path algorithm works, rather than a lucky feature of the drawing.

Negative weights break that reasoning. In a directed graph with $s\to u$ costing $2$, $s\to v$ costing $5$, and $v\to u$ costing $-4$, the Dijkstra algorithm would finalize $u$ at $2$ before discovering the cheaper cost $1$. The Bellman-Ford algorithm handles negative edge weights when no relevant negative directed cycle exists.

With an adjacency list and an indexed binary heap implementing a priority queue, the time complexity is $O((|V|+|E|)\log |V|)$ for $|V|\ge 2$, using Big O notation. Each vertex is extracted at most once, each edge is inspected once per direction, and each successful edge relaxation decreases a heap key in $O(\log |V|)$ time. This assumes constant-cost arithmetic and comparisons; exact computation with very large weights adds their representation cost. The queue uses $O(|V|)$ space beyond the graph. Simply scanning all remaining vertices gives $O(|V{|}^2+|E|)$ instead.^[ref][ref]

The 1959 paper presents the shortest path problem as its second problem, after the minimum spanning tree problem, and grows known shortest routes in increasing distance order.^[ref] In his later recollection, Dijkstra dated the shortest-route discovery to 1956: a demonstration for the ARMAC computer used a simplified Dutch railway map and printed the route between towns. A practical request became an enduring algorithm because the same distance rule applies to any suitable graph.^[ref]

For a finite connected weighted graph with distinct edge weights, Kruskal's algorithm produces the unique minimum spanning tree. If another optimal tree existed, take an edge belonging only to the algorithm's tree and slightly increase its weight without changing the strict edge order. The algorithm then returns exactly the same tree, which must still be optimal, but the other tree's weight is unchanged and is now strictly smaller, a contradiction. Distinct weights are sufficient, not necessary: a triangle with weights $1,1,2$ has a unique optimum formed from the two weight-one edges.

Double every edge of a minimum spanning tree to obtain a connected even-degree multigraph, traverse an Euler circuit, and shortcut repeated vertices. The triangle inequality prevents any shortcut from increasing cost. Deleting an edge of an optimal tour gives a spanning tree, so the minimum spanning tree has cost at most the optimal tour. The returned tour therefore costs at most twice optimum and is computable in polynomial time. In the relative-error convention this is an error-one approximation.

Graph theory studies vertices and the edges connecting them: which graph paths exist, how efficiently we can travel, and which connections are indispensable. A road map becomes a graph when junctions are vertices and road segments are edges; a communications network uses routers and links instead. The drawing helps us see connections, but its apparent lengths need not be the costs being optimized. Record travel times or transmission costs separately in a weighted graph.

The appeal of graph theory is that one model serves many practical questions. Graph paths describe routes, connected components of a graph identify isolated regions, and minimum spanning trees connect all locations cheaply. The shortest path problem asks a different question: find the cheapest journey between specified locations. Our four-vertex example below makes that distinction concrete and shows how the Dijkstra algorithm discovers a route without trying every graph path.

A disjoint-set data structure stores the current partition of a set of vertices into connected components of a graph. The operation $\mathrm{find}(v)$ returns a representative of the block containing $v$. Two vertices are in the same block exactly when their representatives agree. For each candidate edge $uv$, compare $\mathrm{find}(u)$ and $\mathrm{find}(v)$. Equal representatives mean reject; different representatives mean accept and perform $\mathrm{union}(u,v)$, merging the two blocks. The representatives are bookkeeping choices, not preferred vertices of the minimum spanning tree.

Every acceptance reduces the connected component of a graph count by one and increases the accepted edge count by one, preserving $|F|=|V|-c$. Thus the ledger reaches $c=1$ exactly when $|F|=4$. Only ten representative queries and four merges are needed for the five examined edges, counting two queries per examination and using the already found representatives for each merge. Neither breadth-first search nor reconstruction of a graph path is needed for these connectivity queries.

For $n=|V|$ and $m=|E|$, comparison sorting algorithm takes $O(m\log m)$ time for $m\ge 2$, using Big O notation. One simple disjoint-set data structure implementation stores each block as a rooted tree and attaches the smaller block's root below the larger block's root. Whenever a vertex's depth increases, its block size at least doubles, so its depth is at most $\lfloor {\log }_{2}n\rfloor$. Consequently each representative query or merge takes $O(\log n)$ time. Initialization plus the scan costs $O(n+m\log n)$; including sorting algorithm gives $O(n+m\log m+m\log n)$, hence $O(m\log m)$ for a connected input with $n\ge 2$. These are operation bounds, not measured timings.^[ref]

An edge is safe for the current accepted forest $F$ if some minimum spanning tree contains both $F$ and that edge. The loop invariant is that some minimum spanning tree contains every accepted edge. It holds initially for the empty edge set. Suppose the next accepted edge $e$ joins a current connected component of a graph $S$ to its complement. No earlier rejected edge crosses this cut of a graph: once its endpoints are in one connected component of a graph, subsequent merges never separate them. Thus $e$ is a lightest edge across that cut of a graph.

For the short exchange argument, take a minimum spanning tree $T$ containing $F$. If $e$ is absent, adding it creates a fundamental cycle. This graph cycle contains another edge $f$ crossing the same cut of a graph. No edge of $F$ crosses the cut of a graph, so $f$ is not in $F$. Replace $f$ by $e$: the result is a spanning tree containing $F$ and $e$, with no greater total weight because $w(e)\le w(f)$. It is therefore also a minimum spanning tree. This is the minimum spanning tree cut property in the form needed for tied weights.

In the example, $CD$ is safe after rejecting $AC$: the current connected component of a graph $\{A,B,C\}$ has crossing edges $CD,CE,BE$ of weights $4,6,7$. Its cheapest connection is $CD$. The rejected $AC$ is also the unique heaviest edge of the graph cycle $A,B,C,A$, so the minimum spanning tree cycle property excludes it from every optimum.

Negative and zero edge weights are allowed: the comparisons and exchange argument still apply. Ties can give several minimum spanning trees, though they need not; any order among equal-weight edges remains valid. Distinct edge weights guarantee a unique minimum spanning tree. To see why, take the lightest edge $e$ belonging to exactly one of two proposed optima, say $T$. Deleting $e$ from $T$ gives a cut of a graph; the other optimum has a graph path across it, containing an edge $f$ absent from $T$. Hence $w(e)<w(f)$, and replacing $f$ by $e$ improves that other optimum, a contradiction. For disconnected input, process all edges to obtain a minimum spanning forest, one minimum spanning tree per original connected component of a graph; no spanning tree of the whole graph exists.^[ref]

Kruskal's algorithm constructs a minimum spanning tree of a finite connected graph with undirected edges and real edge weights. Start with all vertices and no edges, a forest of isolated vertices. Sort the edges by nondecreasing weight, then accept an edge exactly when its endpoints belong to different current connected components of a graph. Otherwise reject it: the existing graph path between its endpoints would close a graph cycle. Each acceptance merges two connected components of a graph. Stop after $|V|-1$ acceptances, when the forest has become one spanning tree.

This is a greedy algorithm for economical network connection: only the next affordable connection and the current connected components of a graph matter. Unlike Prim's algorithm, which grows one reached tree, Kruskal's algorithm can grow several separate trees before joining them. The essential safeguard is avoiding a graph cycle, rather than simply buying the cheapest fixed number of edges.

Joseph Bernard Kruskal described this rule as Construction A on page 49 of his February 1956 paper, On the shortest spanning subtree of a graph and the traveling salesman problem; page 50 gives an exchange argument for distinct weights.^[ref]

Consider this original connected graph on vertices $A,B,C,D,E$. Its undirected edges, already in increasing weight order, areHere $AB$ means the unordered pair $\{A,B\}$; the weights are dimensionless costs. Accept $AB$ and $BC$, with total $3$. Reject $AC$: its endpoints already have the graph path $A,B,C$, so it would close the graph cycle $A,B,C,A$. Accept $CD$ and $DE$, reaching all five vertices with four edges. The resulting minimum spanning tree isStop here: $CE$ and $BE$ need not be examined. If processing continued, both would be rejected because their endpoints are already in the same connected component of a graph.

Taking the three cheapest edges $AB,BC,AC$ instead gives a graph cycle on $A,B,C$, leaving $D,E$ isolated: it is neither a forest nor a spanning tree. Even taking the four cheapest edges adds only $CD$ and leaves $E$ isolated. A cheap infeasible selection cannot compete with a minimum spanning tree. For this small graph, checking all $\left(\genfrac{}{}{0ex}{}{7}{4}\right)=35$ four-edge subsets gives a direct certificate: among those that are spanning trees, exactly one has minimum cost $12$, namely $T$. The general algorithm avoids this exhaustive search.

Every path in a minimum spanning tree solves the bottleneck shortest path problem between its endpoints. If $e$ is a maximum-weight edge on the tree path, deleting it gives a graph cut separating the endpoints. A competing path with every edge lighter than $e$ would contain a crossing edge $f$; replacing $e$ with $f$ would decrease the tree's total weight, a contradiction. Equal weights cause no problem: the argument excludes a strictly smaller bottleneck and does not require a unique tree.

A forest containing one minimum spanning tree of each connected component of a graph of a finite undirected weighted graph, including isolated vertices. For disconnected input, Kruskal's algorithm returns a minimum spanning forest.

A minimum spanning tree minimizes total edge weight among spanning trees of a connected weighted graph. It can be computed in polynomial time by repeatedly adding the least-weight edge joining two current components. The cut-exchange argument preserves the existence of an optimum containing every accepted edge. Removing an edge of a travelling-salesman tour gives a spanning tree, so its optimum is a lower bound on optimal tour cost.

The unique lightest edge across a cut of a graph belongs to every minimum spanning tree. If a spanning tree omits it, inserting it creates a graph cycle with another edge across that cut of a graph. Removing that heavier edge gives a lighter spanning tree, a contradiction. This proves the correctness of Prim algorithm and Kruskal algorithm for distinct weights.

The unique heaviest edge on a graph cycle belongs to no minimum spanning tree. If a spanning tree contains it, deleting it gives two components; the rest of the graph cycle has a lighter edge across that cut of a graph. Insert that edge to reduce the weight. This is the deletion certificate used by the reverse-delete algorithm.

A minimum-weight perfect matching pairs every vertex exactly once while minimizing total edge weight. General weighted perfect matching has polynomial-time algorithms. In the Christofides algorithm, it corrects precisely the odd-degree vertices of a minimum spanning tree. Alternating edges of a cyclic order on an even number of vertices give two perfect matchings; the cheaper one costs at most half that cycle's cost.

For the metric travelling salesman problem, a tour is a polynomial-size complexity certificate: list the vertices in cyclic visiting order. In polynomial time verify that every vertex occurs exactly once, add the encoded integer edge costs and compare the sum with the threshold. The certificate has $O(n\log n)$ bits, and addition uses a number of bits polynomial in the input length. If validity of the metric input is not treated as a promise, nonnegativity, symmetry and all triangle inequalities can also be checked in polynomial time. Therefore the decision problem belongs to NP.

An evaluation algorithm immediately decides a threshold instance by computing the optimum and comparing it with $L$. Conversely, suppose there is a polynomial-time decision algorithm. The optimum is an integer in $[0,nM]$, where $M$ is the largest edge cost; any fixed cyclic ordering gives the upper bound. Binary search on this interval using threshold queries finds the exact minimum. It makes $O(\log (nM+1))$ queries, and every queried threshold has polynomial encoding length. Thus the time is polynomial in the bit length, even when $M$ is numerically large. Zero-cost and trivial small instances can be handled directly. ConsequentlyThis concerns the optimum value; constructing an optimal tour is the separate optimization task.

For the hardness reduction, start with an undirected graph $G$ on $n\ge 3$ vertices and form the complete graph with costsThese costs satisfy the triangle inequality, since every direct cost is at most two and every two-edge path costs at least two. Set the threshold to $n$. Every tour has exactly $n$ edges, each costing at least one. Hence it has cost at most $n$ precisely when all its edges came from $G$, which is precisely the existence of a Hamiltonian cycle in $G$. The construction and threshold encoding are polynomial-time. Thus the assumed NP-completeness of the Hamiltonian circuit problem gives NP-hardness of metric TSP; together with its NP membership this proves NP-completeness of metric TSP decision.

For the approximation, compute a minimum spanning tree $T$. Deleting any one edge of an optimal tour leaves a spanning tree, so nonnegative costs implyDouble every tree edge. The resulting connected multigraph has even degrees and hence an Euler circuit, of cost $2c(T)$. Traverse it and skip previously visited vertices, except for the final return to the start. Each skip replaces a path by its direct edge; repeated use of the triangle inequality shows that no replacement increases cost. The result is a tour visiting every vertex exactly once and satisfyingThe Euler traversal and shortcutting take polynomial time, so the assumed polynomial-time MST routine supplies the requested polynomial-time algorithm. This is the double-tree approximation for metric TSP. In the relative-error convention, $c/\mathrm{OPT}-1\le 1$ when the optimum is positive, explaining the printed term “1-approximation”; in the multiplicative convention it is a factor-two approximation. If the optimum is zero, the same bound forces the returned tour to have zero cost as well.

For a connected undirected weighted graph, a spanning tree connects all vertices without a graph cycle. A minimum spanning tree minimizes the sum of its edge weights. Disconnected input has no spanning tree, although the same methods produce a minimum spanning forest. Negative edge weights and ties cause no difficulty; a tree always contains exactly $|V|-1$ edges.

The central exchange argument is the minimum spanning tree cut property. Suppose a forest $F$ is contained in some minimum spanning tree $T$, and consider a cut with no edge of $F$ crossing it. Let $e$ be a lightest crossing edge. If $e\notin T$, adding it creates a graph cycle; the graph path in $T$ between its endpoints contains a crossing edge $f$. That $f$ is not in $F$, and $w(e)\le w(f)$. Thus $T-f+e$ is another spanning tree with no larger weight and still contains $F$. It is also minimum and contains $F\cup \{e\}$. This proves that the chosen edge is safe, rather than merely asserting a greedy choice.

Kruskal's algorithm sorts all edges by increasing weight, starts with the empty forest, and adds an edge precisely when its endpoints are in different components. Each added edge is lightest across a component cut respected by the current forest. The exchange proof inductively keeps the forest inside a minimum spanning tree; connectedness makes the final forest a spanning tree, hence an optimum. Sorting takes $O(|E|\log |E|)$ comparisons, and even a simple component-merging implementation takes only polynomial additional work. Efficient component tracking improves that overhead further.

Prim's algorithm instead grows a single tree, repeatedly adding a lightest edge from its vertex set to the outside. The same cut argument proves correctness. A dense implementation using an array runs in $O(|V{|}^2)$ comparisons. The dual minimum spanning tree cycle property says a uniquely heaviest edge of a graph cycle belongs to no minimum spanning tree: exchanging it for a lighter crossing edge strictly improves any tree containing it. Ties must be handled carefully; a merely nonunique heaviest edge can occur in an optimum.

Complexity classes are formally classes of decision problems, so use the version asking whether a graph has a spanning tree of total weight at most a supplied threshold $K$. Assume integer or rational weights and threshold are encoded in binary. The input length includes all these bits, not only the numbers of vertices and edges. P consists of decision problems decidable by a deterministic algorithm in time polynomial in that input length. NP consists of those with polynomial-size complexity certificates verified in deterministic polynomial time, equivalently decidable in polynomial time by a nondeterministic machine.

Kruskal's algorithm constructs the optimum and compares its weight with $K$. Binary integer comparisons and sums are polynomial-time operations. Rational comparisons can be made by cross multiplication, and their summed numerator and denominator have polynomially bounded bit length: a product of input denominators has bit length no greater than the sum of their bit lengths. The combinatorial algorithm makes polynomially many such operations. Hence the minimum-spanning-tree decision problem is in P; the optimization version likewise has a polynomial-time algorithm.

For membership in NP, the complexity certificate is a list of $|V|-1$ selected edges. Check that every edge is present, that the edges connect all vertices and contain no graph cycle, and that their total weight is at most $K$. A graph search and binary arithmetic do this in polynomial time. A successful complexity certificate need not establish that its tree is minimum: it proves the threshold question's yes-answer. Conversely, a yes-instance has such a tree as a complexity certificate. ThereforeMembership in NP does not arithmetic mean NP-hardness; here the explicit greedy algorithm provides the stronger tractability result.

Assume the finite graph is connected, as is necessary for a spanning tree to exist. For a disconnected graph, the same procedures operate separately on its connected components of a graph and produce a minimum spanning forest.

Let $T$ be a minimum spanning tree. If it omitted the unique lightest edge $e$ across the specified cut of a graph, adding $e$ would make exactly one graph cycle: the graph path in $T$ between its endpoints, followed by $e$. Since those endpoints are on opposite sides of the cut of a graph, that graph path contains another crossing edge $f$. Distinct weights give $w_f>w_e$. The graph $T+e-f$ is still a spanning tree, but has smaller total weight, contradicting minimality. Thus every minimum spanning tree contains $e$, the minimum spanning tree cut property.

Prim algorithm starts from one graph vertex, repeatedly choosing the lightest edge from the reached graph vertices to an unreached graph vertex. Connectivity ensures that such an edge exists until all graph vertices have been reached. Each choice adds one new graph vertex and creates no graph cycle. By the minimum spanning tree cut property, every chosen edge belongs to every minimum spanning tree. After $|V|-1$ choices the selected edges form a spanning tree, necessarily a minimum spanning tree.

For Kruskal algorithm, suppose the next accepted edge $e$ joins two different components of the current forest, and let $S$ be one of those components. No previously considered lighter edge crosses $S$: an accepted one already joins graph vertices within a current component, while a rejected one had its endpoints connected when it was rejected and therefore still has them in a single current component. Consequently $e$ is lightest across the cut of a graph defined by $S$. The minimum spanning tree cut property again places every accepted edge in every minimum spanning tree. At termination the accepted forest must be connected, since otherwise a crossing edge of the original connected graph would have been accepted when considered. It is therefore a minimum spanning tree.

This reasoning also proves the minimum spanning tree is unique. Either procedure produces a spanning tree all of whose $|V|-1$ edges belong to every minimum spanning tree; another minimum spanning tree cannot have any different edge.

For the minimum spanning tree cycle property, suppose a spanning tree $T$ contained the unique heaviest edge $e$ of a graph cycle $C$. Removing $e$ splits $T$ into two components. The remainder of $C$ connects the endpoints of $e$, so it contains an edge $f$ across these components. This edge cannot belong to $T-e$, and $w_f<w_e$. Hence $T-e+f$ is a lighter spanning tree. Thus no minimum spanning tree contains $e$.

Finally consider the reverse-delete algorithm, processing edges from largest to smallest weight. Whenever an edge is retained because its deletion would disconnect the current graph, it is a bridge in a graph; deleting other edges later cannot create an alternative path around it, so it remains a bridge in a graph. If a currently processed edge $e$ is deletable, it lies on a current graph cycle. None of that graph cycle's other edges can be an earlier retained heavier edge, since those are bridges in a graph. Thus all other edges on the graph cycle are lighter than $e$. The minimum spanning tree cycle property says that deleting $e$ removes no edge of any minimum spanning tree of the original graph. Throughout, connectivity and the presence of the unique minimum spanning tree are preserved. At termination a surviving graph cycle is impossible: any of its edges was deletable when considered, since that entire surviving graph cycle already existed then. The final connected graph is a tree, and hence is exactly the minimum spanning tree.

Let $C^{\ast }$ be an optimal metric tour. Removing any one of its edges gives a spanning tree, so the minimum spanning tree $T$ satisfies $c(T)\le c(C^{\ast })$. The handshaking lemma shows that its odd-degree set $U$ has even size.

Follow $C^{\ast }$ and retain only vertices of $U$, shortcutting between consecutive retained vertices. This produces a cyclic order on $U$ of total cost at most $c(C^{\ast })$. If $U$ is nonempty, the alternating edges of that cyclic order form two perfect matchings; their costs sum to the cycle cost. One has cost at most $c(C^{\ast })/2$, so a minimum-weight perfect matching $M$ hasFor $|U|=2$, count the same undirected edge twice in the cyclic order; each alternating matching consists of one copy. For $U=\varnothing$, use the empty matching.

The multigraph with edges $T\uplus M$ is connected because it contains $T$. Each odd-degree vertex receives exactly one matching edge, and the other degrees are unchanged, so every degree is even. It therefore has an Euler circuit. Constructively, follow unused edges until returning to the starting vertex; parity prevents getting stuck elsewhere. If unused edges remain, connectivity supplies a vertex of the current circuit incident with one, and its additional closed trail can be spliced into the circuit. Repetition gives a circuit using every edge exactly once, including parallel copies.

Shortcut repeated vertices of this Euler circuit to obtain a metric tour. Its cost is at mostComputing a minimum spanning tree, a minimum-weight perfect matching, an Euler circuit and the shortcut tour is polynomial-time; weighted perfect matching is a standard polynomial-time graph optimization problem. Thus the Christofides algorithm is a $3/2$-approximation algorithm for symmetric metric tours.

At weight $y$ the edges considered are precisely the horizontal edges in row $y$. For $y=1$ all $n$ graph vertices in that row are isolated, so all $n-1$ edges are accepted. For $y\ge 2$, the first $y-1$ graph vertices in that row already belong to the one component built by earlier stages, because vertical columns $1,\dots ,y-1$ have already been processed. The other graph vertices are isolated. Thus the edges with $x<y-1$ would create a graph cycle, and all the edges with $x\ge y-1$ are accepted, successively attaching the remaining graph vertices. The rule isThe selected edges of equal weight have no cycles after the existing component is contracted, so tie ordering does not affect this conclusion. Their combined contribution to the minimum spanning tree cost is