1-tree Created 2026-10-31 Updated 2026-11-05
For a designated root vertex in an undirected complete graph, a 1-tree consists of a spanning tree on all other vertices together with two distinct root-incident edges. It is connected and has exactly one cycle, which passes through the root. Its minimum weight is the cost of an independent minimum spanning tree plus the two cheapest root edges, computable in quadratic time on a dense graph by Prim's algorithm.
Borůvka's algorithm 2026-10-31
Start with isolated vertices. In each round, determine the current connected components of a graph, choose a least-weight outgoing edge for each component, add their union, and recompute the components. With distinct weights, each chosen edge is the unique lightest edge across that component's graph cut. The minimum spanning tree cut property puts every such edge in every minimum spanning tree, so the selected edges remain acyclic. Every nonfinal component has an outgoing edge in a connected input, and merging makes progress until a spanning tree remains. Duplicate choices of the same edge are one set insertion.
Each new component contains at least two old components, so there are rounds. Scanning all edges per round gives time. Equal edge weights require a consistent secondary order to avoid choosing a cycle of tied edges.
Otakar Borůvka formulated the distinct-cost minimum-connection problem in 1926.[ref]
O jistém problému minimálním by Otakar Borůvka. pp. 37–38, opening formulation with positive distinct connection costs
Christofides algorithm Created 2026-10-07 Updated 2026-10-14
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 -approximation algorithm for symmetric metric instances.
Combinatorial optimization 2026-11-05
Combinatorial optimization minimizes or maximizes an objective function over discrete structures such as graph paths, graph matchings, trees or permutations. A weighted minimum spanning tree problem, for example, chooses a tree connecting all vertices and minimizes the sum of its edge weights.
The number of feasible structures can be enormous, but this alone does not prove computational hardness. Minimum spanning trees admit efficient greedy algorithms, whereas the general travelling salesman problem is NP-hard. The useful question is which structural properties allow an algorithm to certify an optimum without explicitly listing every feasible object. Relaxations, dynamic programming and approximation algorithms exploit different kinds of structure.
Sort the edge weights of a minimum spanning tree and of any spanning tree in nondecreasing order. Then for every position. To prove it, fix a threshold and retain the graph's edges of weight at most . If this graph has connected components, contains a spanning forest of each component using those edges: otherwise a light edge joining two of its pieces could replace an edge heavier than on its tree path, decreasing total weight. Hence exactly edges of have weight at most . No other spanning tree can have more, since its retained edges form a forest inside those components. These threshold counts imply the coordinatewise inequality for sorted weights.
Cut lemma for minimum spanning trees 2026-10-31
Let an edge set be contained in some minimum spanning tree, and let a cut of a graph have no crossing edge in . Any least-weight edge crossing that cut of a graph can be added to while preserving its containment in some minimum spanning tree. Insert the chosen edge into an optimum containing , then remove another crossing edge from the resulting graph cycle; it is no lighter and cannot belong to . Ties imply existence of an optimum containing the chosen edge, rather than membership in every optimum.
Dijkstra algorithm 2026-10-14
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 and 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 discovers at , at , and at . Choose next: edge relaxation through lowers to and to . Choose : edge relaxation through lowers to . Finally choose . The permanent distances are therefore , , , ; the evolving tentative distances were and .
Tentative distances fall until the Dijkstra algorithm makes each label permanent
. Details. 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:
| Vertex | Distance from | Shortest-path predecessor | Finalization order |
|---|---|---|---|
| None: source | |||
Following shortest-path predecessors backwards gives ; reversing the order gives . If only this destination matters, stop when is finalized. Stopping when is first discovered would incorrectly return . If the smallest remaining tentative distance is , all remaining vertices are unreachable.
Why is the permanent choice safe? Suppose the selected vertex had a cheaper graph path. Let be the first unfinalized vertex on that graph path. Its preceding vertex was finalized, so edge relaxation has already offered 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 . 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 costing , costing , and costing , the Dijkstra algorithm would finalize at before discovering the cheaper cost . 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 for , 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 time. This assumes constant-cost arithmetic and comparisons; exact computation with very large weights adds their representation cost. The queue uses space beyond the graph. Simply scanning all remaining vertices gives instead.[ref]
https://algs4.cs.princeton.edu/44sp/DijkstraSP.java.html. Princeton, DijkstraSP implementation
[ref]https://algs4.cs.princeton.edu/code/javadoc/edu/princeton/cs/algs4/IndexMinPQ.html. Princeton, indexed binary heap operations
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]
https://www.cs.yale.edu/homes/lans/readings/routing/dijkstra-routing-1959.pdf. Dijkstra, A note on two problems in connexion with graphs, pp. 269–271
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]https://garfield.library.upenn.edu/classics1983/A1983QA19900001.pdf. Dijkstra's recollection, published in 1983
Distinct weights imply a unique minimum spanning tree Created 2026-10-25 Updated 2026-10-31
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 has a unique optimum formed from the two weight-one edges.
Double-tree approximation for metric TSP 2026-10-14
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.
Edsger W. Dijkstra Created 2026-10-24 Updated 2026-11-05
Edsger W. Dijkstra was a computer scientist whose work includes the Dijkstra algorithm for shortest paths with nonnegative edge weights. Its key step finalizes the unsettled vertex with the smallest tentative distance; nonnegative edge weights ensure that a later route cannot improve that distance.[ref]
The same short paper also treated the minimum spanning tree problem. The distinction is instructive: minimizing the total weight of a connecting tree differs from minimizing routes from a source. Dijkstra later recalled devising the shortest-path example for a 1956 computer demonstration using a simplified Dutch railway map, a concrete explanation of the computational task for a general audience.[ref]
Reflections on A Note on Two Problems in Connexion with Graphs by Edsger W. Dijkstra. EWD841a, recollection of the 1956 demonstration
Portrait of Edsger W. Dijkstra
. Hamilton Richards. CC BY-SA 3.0, via Wikimedia Commons. Source. Graph algorithm 2026-11-05
A graph algorithm computes a property of a graph or constructs a related object from its graph vertices and graph edges. The input representation matters: an adjacency list lets an algorithm inspect the neighbours of one graph vertex without scanning every possible pair of graph vertices, whereas an adjacency matrix provides direct tests for individual graph edges.
For example, breadth-first search finds every graph vertex reachable from a starting graph vertex . Mark , place it in a FIFO queue, then repeatedly remove the oldest marked graph vertex and mark/enqueue each previously unmarked neighbour. A graph vertex is enqueued at most once, so scanning adjacency lists costs . The FIFO queue processes distance layers in order; the first discovery of a graph vertex supplies a shortest graph path in an unweighted graph.
For graph edges , , , starting at discovers before , with distances . The same graph can support different questions: depth-first search investigates traversal structure, Dijkstra's algorithm uses nonnegative edge weights for shortest graph paths, and a minimum spanning tree minimizes the total weight needed to connect an undirected graph. Matching the algorithm to its assumptions is part of modelling the problem.
Graph theory Created 2026-09-24 Updated 2026-10-13
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.
Kruskal component merging 2026-10-18
A disjoint-set data structure stores the current partition of a set of vertices into connected components of a graph. The operation returns a representative of the block containing . Two vertices are in the same block exactly when their representatives agree. For each candidate edge , compare and . Equal representatives mean reject; different representatives mean accept and perform , merging the two blocks. The representatives are bookkeeping choices, not preferred vertices of the minimum spanning tree.
Connected components of a graph merge only when an edge is accepted
. The same example as a disjoint-set data structure ledger. Each coloured band is one block of the current partition of a set. The rejection of leaves both the partition of a set and the running cost unchanged. Bands show membership, not internal representative pointers. Details.Every acceptance reduces the connected component of a graph count by one and increases the accepted edge count by one, preserving . Thus the ledger reaches exactly when . 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 and , comparison sorting algorithm takes time for , 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 . Consequently each representative query or merge takes time. Initialization plus the scan costs ; including sorting algorithm gives , hence for a connected input with . These are operation bounds, not measured timings.[ref]
WeightedQuickUnionUF.java. Robert Sedgewick and Kevin Wayne, Algorithms, 4th edition, companion WeightedQuickUnionUF.java: class documentation and union method; union by size without path compression, linear initialization and logarithmic operations
Kruskal safe edge 2026-10-18
An edge is safe for the current accepted forest if some minimum spanning tree contains both 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 joins a current connected component of a graph 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 is a lightest edge across that cut of a graph.
For the short exchange argument, take a minimum spanning tree containing . If is absent, adding it creates a fundamental cycle. This graph cycle contains another edge crossing the same cut of a graph. No edge of crosses the cut of a graph, so is not in . Replace by : the result is a spanning tree containing and , with no greater total weight because . 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, is safe after rejecting : the current connected component of a graph has crossing edges of weights . Its cheapest connection is . The rejected is also the unique heaviest edge of the graph cycle , 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 belonging to exactly one of two proposed optima, say . Deleting from gives a cut of a graph; the other optimum has a graph path across it, containing an edge absent from . Hence , and replacing by 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]
KruskalMST.java. Robert Sedgewick and Kevin Wayne, Algorithms, 4th edition, companion KruskalMST.java, class documentation and constructor: arbitrary signed weights, ties, disconnected input and sorted processing
Kruskal's algorithm Created 2026-10-14 Updated 2026-10-18
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 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]
https://langevin.univ-tln.fr/cours/graphe/bonus/Krukskal.pdf. Joseph B. Kruskal, Jr., Proceedings of the American Mathematical Society 7(1), February 1956, pp. 48–50; inspected scan, Construction A and final exchange argument
Kruskal's algorithm worked example 2026-10-18
Consider this original connected graph on vertices . Its undirected edges, already in increasing weight order, areHere means the unordered pair ; the weights are dimensionless costs. Accept and , with total . Reject : its endpoints already have the graph path , so it would close the graph cycle . Accept and , reaching all five vertices with four edges. The resulting minimum spanning tree isStop here: and 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 instead gives a graph cycle on , leaving isolated: it is neither a forest nor a spanning tree. Even taking the four cheapest edges adds only and leaves isolated. A cheap infeasible selection cannot compete with a minimum spanning tree. For this small graph, checking all four-edge subsets gives a direct certificate: among those that are spanning trees, exactly one has minimum cost , namely . The general algorithm avoids this exhaustive search.
Light edge crossing a cut 2026-10-31
An edge of minimum edge weight among those crossing a specified cut of a graph. It exists when the crossing set is nonempty. Several tied edges can all be light; lightness does not imply uniqueness or membership in every minimum spanning tree.
Maximum spanning tree 2026-10-31
A spanning tree with greatest total edge weight. Apply Kruskal's algorithm in decreasing weight order, or negate every edge weight and compute a minimum spanning tree. Every graph path within a maximum spanning tree solves the widest path problem between its endpoints.
Every path in a minimum spanning tree solves the bottleneck shortest path problem between its endpoints. If 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 would contain a crossing edge ; replacing with 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.
Minimum spanning forest 2026-10-18
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.



