Algorithms on graphs

Explanation

• A spanning tree of a connected network on $n$ vertices uses every vertex and exactly $n-1$ arcs and contains no cycle; the minimum spanning tree, or minimum connector, is the one of least total weight.
• Kruskal's algorithm sorts every arc into ascending order of weight and then adds arcs one at a time, rejecting any arc that would form a cycle, stopping once $n-1$ arcs are in the tree.
• Prim's algorithm grows a single tree from a chosen start vertex: at each stage it adds the shortest arc joining a vertex already in the tree to a vertex not yet in it, and it never needs a cycle check because one endpoint is always outside the tree.
• Prim's algorithm also runs directly on a distance matrix: delete the row of the newly connected vertex, label its column, and scan every labelled column for the smallest uncrossed entry.
• Both algorithms return a tree of the same minimum weight, though the arcs may be listed in a different order and different trees of equal weight can occur when weights are repeated.

Explanation

• Dijkstra's algorithm finds the shortest path from one start vertex to every other. Each vertex carries a box with three entries: the order of labelling, the final label, and a list of working values.
• Give the start vertex final label $0$, then repeatedly choose the smallest working value anywhere in the network, make it final,
• and update every unlabelled neighbour with the sum of the new final label and the connecting arc, recording the new value only if it beats the values already there. To recover the route, trace back from the end vertex, keeping an arc $XY$ whenever the final label of $Y$ minus the final label of $X$ equals the weight of $XY$.
• Floyd's algorithm instead finds the shortest distance between every pair. Start with the distance matrix and a route matrix whose column $j$ is filled with $j$.
• On iteration $k$ compare each entry $d_{ij}$ with $d_{ik}+d_{kj}$; if the route through $k$ is shorter, replace $d_{ij}$ and set the route entry $r_{ij}$ to $r_{ik}$. Iteration $k$ works on the $k$th row and column, and after $n$ iterations the matrices are complete.