Задача Прима-Краскала

Дана плоская страна и в ней n городов. Нужно соединить все города телефонной связью так, чтобы общая длина телефонных линий была минимальной. В декартовой системе координат положение i-го города, i = 1,...,n, задано парой координат (x[i],y[i]). d[i,j] - декартово расстояние между i-ым городом и j-ым городом , j=1,...,n. В задаче речь идет о телефонной связи, т. е. подразумевается транзитивность связи: если i-й город связан с j-ым, а j-ый с k-ым, то i-й связан с k-ым.

Источник: http://pkgn.ru/do/TRPP/TrppKurs.pdf Алгоритм Краскала

Список заданий


© 2018. All rights reserved.