Сравнение алгоритмов полного перебора и модифицированного варианта Прима. В отличии от оригинального алгоритма Прима построение пути осуществляется от одной последней вершины. Т.е. берем случайную случайную вершину, присоединяем к ней ближайшую не присоединенную, в дальнейшем из не присоединенных вершин выбираем ближайшею к последней присоединенных.

Разница в скорости налицо:

А еще этот алгоритм работает неправильно. Полный перебор находит все же более короткий путь:

Код лежит тут.