Я застрял в следующей задаче:
кратчайший путь длины k : ориентированный граф с весовой функцией W: VxV-> R и двумя вершинами s, т.
решение: кратчайший путь (сумма весов на ребрах) длины ровно k от s до t (если существует)
k-медиана : n действительных чисел X1,..., Xn (отличаются друг от друга)
решение: k действительных чисел M1, ..., Mk, которое минимизирует сумму расстояний от каждой входной точки до центра, ближайшего к этой точке.
Мне нужно сделать сокращение ко второй проблеме, используя первую проблему в качестве черного ящика.
Я пытался построить граф и сделать так, чтобы каждому действительному числу Xi соответствовала вершина Vi, но я не являюсьуверен, как продолжить. Я думаю, что мне нужно добавить больше вершин, но не знаю, сколько и как их использовать.