Kruskal's and Prim's algorithms for minimum spanning trees, Dijkstra's algorithm for the shortest path, and the route inspection and travelling salesperson problems.

What this dot point is asking

AQA wants you to apply Kruskal's and Prim's algorithms to find a minimum spanning tree, use Dijkstra's algorithm to find the shortest path between two vertices, solve the route inspection (Chinese postman) problem, and find upper and lower bounds for the travelling salesperson problem.

Minimum spanning trees

Prim's algorithm reaches the same tree by a different route: it grows a single connected tree outward from a chosen start vertex, at each step adding the cheapest edge that joins a new vertex to the tree so far. Prim's never needs an explicit cycle check, because it only ever reaches out to vertices not yet included, which makes it well suited to the matrix form of the algorithm where you cross out columns as vertices join.

Dijkstra's algorithm

Both algorithms always return a minimum spanning tree, but they suit different question formats. Kruskal's works from a sorted edge list and is natural when the network is given as a list of weighted edges; its only subtlety is the cycle check, usually done by tracking which vertices are already joined into the same component. Prim's works from the network's distance matrix, crossing out the column of each newly added vertex and scanning the rows of the joined vertices for the smallest uncrossed entry, which makes it the method examiners pair with a matrix presentation. When edge weights are all distinct the minimum spanning tree is unique, so both algorithms must produce the same tree, a fact you can use to check your work.

Route inspection and travelling salesperson

Route inspection (the Chinese postman problem) finds the least total distance of a closed route that traverses every edge at least once. If every vertex has even degree the network already has an Eulerian circuit and no edge needs repeating, so the answer is just the sum of all edge weights. Otherwise you list the odd-degree vertices (there is always an even number of them), pair them up in every possible way, find the shortest path between each pair, and choose the pairing whose total is smallest. That smallest total is the extra distance added to the sum of all edges, because those paths are the edges you walk twice.

The travelling salesperson problem visits every vertex exactly once and returns to the start with least total distance, and unlike route inspection it has no efficient exact algorithm, so the exam asks for bounds instead. The nearest-neighbour algorithm gives an upper bound: start at a vertex, repeatedly go to the nearest unvisited vertex, then return to the start. A lower bound comes from deleting one vertex, finding a minimum spanning tree of the remaining network, and adding back the two shortest edges from the deleted vertex. The true optimum lies between the best lower bound and the best upper bound, and a question is effectively solved when the two bounds coincide.