EDIT: offenbar ich auf einem Link geklickt, weil ich dachte, dass ich auf eine neue Frage beantworten; ignorieren Sie dies, wenn - wie sehr wahrscheinlich - diese Frage für Sie nicht mehr wichtig ist.
Angesichts der eingeschränkten Version des Problems, mit dem Sie es zu tun haben, wird dies viel einfacher zu implementieren. Das Wichtigste ist, dass in Bäumen die kürzesten Pfade die einzigen Pfade zwischen zwei Knoten sind. Also, was Sie tun, ist alle Paare kürzeste Wege zu lösen, die O(n²) in Bäumen ist, indem Sie n BFS-Traversalen, und dann erhalten Sie die k minimale Werte. Dies kann wahrscheinlich in irgendeiner Weise optimiert werden, aber der naive Ansatz dazu ist, die O(n²) Abstände in O(n² log n) Zeit zu sortieren und die k kleinsten Werte zu nehmen; Mit etwas Buchhaltung können Sie verfolgen, welche Entfernung zu welchem Pfad ohne Zeitaufwand Overhead entspricht. Dies ergibt eine bessere Komplexität als die Verwendung eines KSPA-Algorithmus für O(n²) mögliche s-t-Paare.
Wenn das, was Sie tatsächlich eine Quelle gemeint Festsetzung und erhalten die k Knoten mit dem kleinsten Abstand von dieser Quelle, ein BFS tun. Falls Sie sowohl Quelle als auch Ziel fixieren wollten, reicht ein BFS aus.
Ich sehe nicht, wie man die Tatsache nutzen, dass alle Kanten von einem Knoten auf den Knoten in der Ebene darunter das gleiche Gewicht gehen, ohne mehr über die Struktur des Baumes zu kennen.
Die Lösungen, die in den K-kürzesten Pfadfindungsalgorithmen vorgeschlagen werden, soweit ich sehen kann, beschäftigen sich mit Graphen im Allgemeinen. Aber was ich vor mir habe, hängt eher damit zusammen, die kürzesten Pfade in einem Baum zu finden, wo Sie in jedem Schritt die gleichen Optionen (mit den gleichen Gewichten) für alle Knoten auf der gleichen Ebene haben. – Fungsten