A graph consists of nodes and edges. Each edge in our example has a positive weight, or cost: it might represent distance, time or energy. We use undirected, connected graphs, so every node can be reached from every other node.
The same network raises different questions. Dijkstra finds least-cost paths from a starting node. Prim and Kruskal instead find a tree connecting all nodes without cycles and with the smallest possible sum of weights. A shortest path and a minimum spanning tree are not the same object.
One small shared example
Consider four nodes A, B, C, D with edges A–B of weight 4, A–C of weight 2, B–C of weight 1, B–D of weight 5 and C–D of weight 8. From A to D, path A–C–B–D costs 2+1+5=8; A–B–D costs 9 and A–C–D costs 10. A minimum spanning tree takes B–C, A–C and B–D, for total weight 1+2+5=8. The matching number 8 is a coincidence: the first problem measures one route, while the second measures a network connecting everyone.
1. Dijkstra: settle increasingly certain distances
Assign distance 0 to the start and tentative distance infinity to every other node. At each step, choose the unsettled node with the smallest tentative distance. Then try to improve each neighbour by adding the connecting edge weight. With non-negative weights, the chosen distance is final. In the small example, from A we discover C at cost 2 and B at cost 4; through C we improve B to 3; through B we reach D at cost 8.
Important limit: this reasoning does not generally work with negative weights.
2. Prim: grow a tree
Choose a starting node. At each step, take the lightest edge joining a node already in the tree to one outside it. The connected group grows without creating cycles until it includes every node. Prim always looks at the boundary of the current tree: its choice depends on what has already been built.
3. Kruskal: sort edges and avoid cycles
Sort all edges from lightest to heaviest. Accept an edge if it joins two previously separate groups; reject it if it would close a cycle. The groups gradually merge into one tree. Prim and Kruskal can choose different edges when weights tie, but the minimum total weight agrees.
Try the same graph
In the interactive weighted-graph laboratory, generate a connected random graph with 20–100 nodes and integer weights from 1 to 20. A seed reproduces the same graph; choose start and target for Dijkstra, then compare Prim and Kruskal on that same network. Advance one step at a time or play the animation. Node positions help readability, but the visual length of an edge is not its weight.
What to compare
For Dijkstra, watch a tentative distance improve and then become final. For Prim and Kruskal, compare the final total weight: it should agree even if the order of choices differs. On a large graph you can hide weight labels to see the structure more clearly; the examined edge weight remains visible.