D1.2 - Algorithms on graphs
- Syllabus
- 2019
- Topic
- D1.2
- Level
- AS
Learning objectives
D1.2.1Minimum spanning treeThe minimum spanning tree Matrix representation for Prim’s algorithm is expected. (minimum connector) problem.; Drawing a network from a given matrix and writing down Prim’s and Kruskal’s algorithm. the matrix associated with a network will be involved.D1.2.2Dijkstra’s algorithm for finding the shortest pathDijkstra’s algorithm for finding the shortest path.
Build a minimum spanning tree
A spanning tree connects every vertex of a connected weighted graph without cycles. With n vertices it has exactly n−1 edges. A minimum spanning tree (MST), or minimum connector, is a spanning tree whose total edge weight is as small as possible.
| Method | Selection rule | Stop |
|---|---|---|
| Kruskal | consider edges in increasing weight order; add an edge only if it does not create a cycle | n−1 edges have been selected |
| Prim | start at the stated vertex; repeatedly choose the smallest edge joining the current tree to a new vertex | every vertex has joined the tree |
For Prim on a symmetric adjacency matrix, activate the start vertex's column and remove its row from future selection. Choose the least available entry in active columns; it identifies an edge to the vertex in that row. Activate the new vertex's column, remove its row, and repeat. Rows and columns represent vertices, symmetric entries represent undirected edge weights, and a blank or dash means no edge.
If AB=2, AC=5, BC=1, BD=4 and CD=3, Kruskal selects BC, AB, CD, with total 6. Prim from A selects AB, BC, CD: the order differs, but the MST is the same.
Prim must choose the smallest edge crossing from the current tree to an unjoined vertex, not simply the smallest edge anywhere. An MST minimises the total weight needed to connect all vertices; it is not the shortest path between a chosen pair. Equal weights may allow more than one MST.
Find a shortest path with Dijkstra's algorithm
Dijkstra's algorithm finds shortest distances from one start vertex in a weighted network with non-negative edge weights. A temporary label is the best distance found so far; once it is the smallest temporary label and becomes permanent, its value cannot improve.
Give the start vertex permanent label 0 and every other vertex a temporary label ∞. From the newest permanent vertex u, calculate a candidate for each adjacent non-permanent vertex v. Replace v's label and predecessor only when the candidate is smaller. Then make the smallest temporary label permanent and repeat until the destination is permanent.
\text{candidate label for }v=\text{permanent label of }u+w(u,v)
Let AB=4, AC=2, CB=1, BD=5, CD=8, BE=9 and DE=2. From A, make C permanent at 2, improve B to 3 via C, make B permanent, improve D to 8, then reach E at 10 via D. Backtracking predecessors gives A−C−B−D−E, length 10.
The permanent destination label gives the shortest distance, but the route comes from predecessor labels: start at the destination and follow predecessors backwards to the start, then reverse the sequence. If a journey must pass through a specified vertex, find and join the required shortest-path segments.
Do not choose the smallest edge weight; choose the vertex with the smallest total temporary label. Never change a permanent label, and do not confuse the resulting shortest path with a minimum spanning tree, which connects every vertex rather than one chosen pair.