A while ago I had a problem with the MST algorithm in boost. Essentially profiling reviled that the MST algorithm was a bottleneck for the computation I was performing. Thus I had to investigate the performance bottlenecks in boost mst and with this mail I want to investigate the potential for improving current boost implementation. What is the proposed way of getting the prim algorithm updated in boost? First let me argue that there is room for improvement. I have made a test program that constructs 1000 random complete graphs with 1000 nodes and the execution time is as follows actually implementing jarniks algorithm prim_minimum_spanning_tree 47.585s current prim (djikstra wrapper) 3m2638s (338% slower) kruskal_minimum_spanning_tree 40m57s (5063% slower) The 47.585s performance is achieved by just implementing Jarnik/Prims algorithm using the relaxed_heap (that is already in boost, but code is available if necessary). As a side effect it seems to be a good test for the relaxed_heap, given that it revealed problems with the Fibonacci heap[1]. 1. http://lists.boost.org/boost-users/2006/07/20876.php I also want to take the opportunity to ask about the meaning of the minimum spanning tree algorithm as such, since efficient implementations in the future could be helped a lot by knowing exactly what the problem that should be solved is. Given the hardness to understand the actual generality of the MST problem the current implementation tries to solve, I find it difficult to see how efficient algorithms can be heuristically selected. I.e. can you use num_edges(g) as an indicator of sparseness? -- Magnus Ekdahl