Spanning trees & shortest path
Practice Flashcards
Flip to reveal answersWhat is a minimum spanning tree (MST)?
Track your progress — Sign up free to save your progress and get smart review reminders based on spaced repetition.
All 8 Flashcards — Spanning trees & shortest path
Sign up free to track progress and get spaced-repetition review schedules.
Question
What is a minimum spanning tree (MST)?
Answer
The set of edges connecting every vertex with the least total weight and no cycle. On n vertices it has exactly n − 1 edges.
Question
How many edges does a spanning tree on n vertices have?
Answer
Exactly n − 1, and it contains no cycle.
Question
State Kruskal's algorithm.
Answer
Sort all edges from cheapest to dearest; add them one at a time, skipping any edge that would create a cycle, until all vertices are connected.
Question
State Prim's algorithm.
Answer
Start at any vertex; repeatedly add the cheapest edge that joins a new (un-included) vertex to the tree, until all vertices are included.
Question
Do Prim's and Kruskal's give the same answer?
Answer
They always give the same total weight (and the same tree when all edge weights are distinct).
Question
What does Dijkstra's algorithm find?
Answer
The shortest path (least total weight) from a start vertex to a target vertex — not the whole connecting tree.
Question
In Dijkstra's, how is a vertex's label updated?
Answer
new label = min(old label, permanent value of current vertex + edge to this vertex). The smallest temporary label becomes permanent next.
Question
MST vs Dijkstra — when do you use each?
Answer
MST (Prim/Kruskal): connect ALL vertices cheaply. Dijkstra: shortest route between TWO specific vertices.
Read the notes
Full study notes for Spanning trees & shortest path
Topic 3.16 hub
Route algorithms (HL only)
More from Topic 3.16
All flashcards in this topic
Math AI exam skills
Paper structures & tips
Track your progress with spaced repetition
Sign up free — Aimnova tells you exactly which cards to review and when, so you remember everything before your IB exam.
Start Free