EDIT: apparemment je cliqué sur un lien, parce que je pensais que je répondais à une question nouvelle; ignorez ceci si - comme c'est très probable - cette question n'est plus importante pour vous. Compte tenu de la version restreinte du problème que vous traitez, cela devient beaucoup plus simple à implémenter. La chose la plus importante à remarquer est que dans les arbres, les chemins les plus courts sont les seuls chemins entre deux nœuds. Donc, ce que vous faites est de résoudre tous les chemins les plus courts des paires, qui est O(n²) dans les arbres en faisant n traversées BFS, et puis vous obtenez les valeurs minimales k. Cela peut probablement être optimisé d'une certaine façon, mais l'approche naïve de faire cela est de trier les O(n²) distances en O(n² log n) temps et prendre les plus petites valeurs k; avec un peu de tenue de livres, vous pouvez garder une trace de la distance qui correspond à quel chemin sans temps de complexité. Cela vous donnera une meilleure complexité que l'utilisation d'un algorithme KSPA pour O(n²) paires de t-t possibles.
Si ce que vous vouliez dire en fait est la fixation d'une source et obtenir les k noeuds avec la plus petite distance de cette source, un BFS fera. Dans le cas où vous vouliez réparer à la fois la source et la cible, un seul BFS est suffisant.
Je ne vois pas comment vous pouvez utiliser le fait que tous les bords allant d'un noeud aux noeuds du niveau inférieur ont le même poids sans en savoir plus sur la structure de l'arbre.
Les solutions proposées dans les algorithmes de recherche de chemin K-plus court autant que je peux voir, traitent des graphiques en général. Mais ce à quoi je fais face est plus lié à la recherche des chemins les plus courts dans un arbre où à chaque pas vous avez les mêmes options (avec les mêmes poids) pour tous les nœuds du même niveau. – Fungsten