Algorithm 422: minimal spanning tree H

This algorithm generates a spanning tree of minimal total edge length for an undirected graph specified by an array of inter-node edge lengths using a technique suggested by Dijkstra 1. Execution time is proportional to the square of the number of nodes of the graph; a minimal spanning tree for a graph of 50 nodes is generated in 0.1 seconds on an IBM System 360/67. Previous algorithms 2, 3, 4, 5 require an amount of computation which depends on the graph topology and edge lengths and are best suited to graphs with few edges.