@SmaiL

Каким алгоритм сделать остов неориентированного взвешенного графа с весами на ребрах и вершинах?

Добрый день. Вопрос задан некорректно, может быть, но все же. Есть значит граф неориентированный. Представим, что это точки на карте. Веса на ребрах - расстояния меж ними. НО. У каждой точки будет, скажем, коэффициент приоритетности от 1 до 10. Так же у меня есть бюджет, который позволяет обойти не все точки. В итоге нужен алгоритм, который бы построил остов графа учитывая расстояние меж точками + важность данной точки? Пробежался по основным алгоритмам (Краскала, Прима, Борувки), но они не учитывают "важность точки", которую нужно посетить.
  • Вопрос задан
  • 125 просмотров
Пригласить эксперта
Ответы на вопрос 1
longclaps
@longclaps
Остовный граф содержит все вершины исходного.
Таким образом, важность вершин не колышет.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через TM ID
Похожие вопросы