Prim’s AlgorithmThe following is an online version of my Prim program for RISC OS computers. Given a table of distances, Prim’s algorithm calculates the minimum spanning tree for the network; ie. the shortest number of paths that join every node together.
The diagram on the right shows an example network with distances marked. The table of this network would be of the following form:
Manchester,41,20,59 Oxford,20,48 Keele,24 Coverack
The first item on each line is the name of the node, then the following numbers are the distance from that node to each of the following nodes. For example, in the above table, the distance from Manchester to Oxford is 41, and the distance from Oxford to Coverack is 48.