РЕДАКТИРОВАТЬ: по-видимому, я нажал на ссылку, потому что я думал, что отвечаю на новый вопрос; игнорируйте это, если - как это очень вероятно - этот вопрос больше не важен для вас.
Учитывая ограниченную версию проблемы, с которой вы имеете дело, это становится намного проще реализовать. Самое важное, на что следует обратить внимание, это то, что в деревьях кратчайшие пути являются единственными путями между двумя узлами. Итак, что вы делаете, это решаете все пары кратчайших путей, которые O(n²) в деревьях, выполняя n обходы BFS, и затем вы получаете k минимальные значения. Это, вероятно, можно оптимизировать каким-то образом, но наивный подход для этого заключается в сортировке расстояний O(n²) за O(n² log n) времени и принятии k наименьших значений; с помощью некоторого учета вы можете отслеживать, какое расстояние соответствует какому пути, без затрат времени. Это даст вам большую сложность, чем использование алгоритма KSPA для O(n²) возможных s-t-пар.
Если вы действительно имели в виду исправление источника и получение узлов k с наименьшим расстоянием от этого источника, подойдет одна BFS. Если вы хотите исправить и источник, и цель, достаточно и одной BFS.
Я не понимаю, как вы можете использовать тот факт, что все ребра, идущие от узла к узлам на уровне ниже, имеют одинаковый вес, не зная больше о структуре дерева.