Dijkstra-Prim Method¶

Definition¶

The Dijkstra-Prim method constructs a minimum spanning tree in a connected undirected network with nonnegative edge lengths. Let $U$ be the set of vertices reached so far; start with $U$ containing one arbitrary vertex and no selected edges. Repeatedly select a shortest edge joining a vertex in $U$ to a vertex outside $U$, add that edge, and add the outside endpoint to $U$. Stop when every vertex belongs to $U$.

Interpretation¶

The method grows one connected tree from a start vertex. Each step adds the cheapest edge that brings in a vertex not yet reached, so the selected edges never form a cycle and never fall apart into separate pieces.

The numbers in brackets give the order of selection when the method starts at $A$: first $A-C$ (2), then $C-B$ (1). The oval marks $U=\{A,B,C\}$ after these two steps. The edges leaving $U$ are $B-D$ (5), $C-D$ (8) and $C-E$ (10), so $B-D$ is chosen next; $A-B$ is no longer a candidate because both its ends are in $U$. Then $D-E$ and $E-F$ follow, for a total length of 13.

Only edges between $U$ and the rest are compared: an edge inside $U$ would close a cycle, and an edge with neither end in $U$ would start a second piece. The cheapest crossing edge is a safe choice: every spanning tree uses at least one edge between $U$ and the rest, and one can show that a cheapest such edge always belongs to some minimum spanning tree.

The shortest path algorithm grows a set $U$ in the same way but compares $d(u)+\ell_{uv}$${\ell }_{uv}$, the full distance from the origin, instead of the length of the edge $u-v$ alone. Mixing up the two is a common slip: the Dijkstra-Prim method minimizes the total length of the tree, not the distance from the start vertex.

Key Results¶

• Compare edges crossing from the whole set $U$, not only from the last added vertex.
• Ties can be broken arbitrarily.
• The starting vertex can change the construction order without changing the minimum total value.

Examples¶

In the figure, each green edge label gives its weight and selection step in brackets. After reaching $U=\{A,B,C\}$$\{A,B,C\}$, $BD=5$ is cheaper than $CD=8$ or $CE=10$$10$; $AB$ is ineligible because both endpoints are already in $U$. The five selected edges have total length 13.

• In the Euclidean example, starting with $U=\{1\}$ selects edge $1-7$ of length $\sqrt{13}$.
• The next edge is $1-4$$4$, of length 5.

Prerequisites¶

• Minimum Spanning Tree

Related Concepts¶

• Kruskal Method
• Shortest Path Algorithm

Sources¶

• OR Modelling · Week 4

Aliases: Prim-Jarník algorithm, Jarník's algorithm, Prim's method Keywords: Prim's algorithm Symbols: square root

Last updated: 20 October 2026 03:02