Choose an edge across the tree boundary
Prim’s algorithm starts from a vertex in an undirected weighted graph and repeatedly selects the lightest edge crossing from the current tree’s vertex set to the outside. It constructs a minimum spanning tree and permits negative edge weights. The candidate edge can leave any vertex already in the tree, not just the most recently added one. Although an arbitrary starting vertex is used, the output is not a shortest-path tree rooted there. The objective is the total weight of the spanning tree, so the shape of the traversal should not be confused with a source-distance calculation.
Maintain the whole frontier
Use A−B=2, A−C=3, B−C=1, B−D=4 and C−D=5, starting at A. First select A−B. With {A,B} in the tree, choose B−C=1 from the updated frontier. Finally choose B−D=4, for total weight 7. Restricting the last step to an edge out of the most recently added vertex C would choose the more expensive C−D=5. Each newly included vertex contributes outgoing candidates, while old candidates whose endpoints are now both inside the tree must no longer be accepted.
A key is not a source distance
In an eager vertex-key implementation, an outside vertex v stores the minimum weight of one edge connecting it to the current tree. This is not Dijkstra’s accumulated distance g(v) from a source. The distinction explains both the different optimization objective and why negative edge weights do not cause the same finalization problem. Sharing a priority-queue data structure does not make two algorithms equivalent. Record the connecting parent edge whenever a key improves so that the final tree can be reconstructed rather than returning only a sequence of selected vertex names.
Select a suitable implementation
With adjacency lists and a binary heap supporting vertex-key updates, the usual bound is O(E log V). A lazy edge-queue implementation retains outdated candidates and has different queue-space and operation counts. Dense graphs can instead use an O(V²) array or matrix implementation. A single start vertex covers only its connected component; disconnected input requires either reporting that fact or restarting in each remaining component to construct a forest. Tied weights may produce several valid trees. Tests should verify connectivity, absence of cycles and minimum total weight rather than insisting on one arbitrary tie-breaking sequence.