Дискретная математика, поиск кратчайшего пути.

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

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

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

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

Subscribe to Заметочки

Don’t miss out on the latest issues. Sign up now to get access to the library of members-only issues.
jamie@example.com
Subscribe