search of the K-first short paths algorithm

I have found many algorithms and approaches that talk about finding th开发者_高级运维e shortest path or the best/optimal solution to a problem. However, what I want to do is an algorithm that finds the first K-shortest paths from one point to another. The problem I'm facing is more like searching through a tree, when in each step you take there are multiple options each one with its weight. What kinds of algorithms are used to face this kind of problems?

---

There is the 2006 paper by Jose Santos comparing three different K-shortest path finding algorithms.

---

Yen's algorithm implementation: http://code.google.com/p/k-shortest-paths/

Easier algorithm & discussion: Suggestions for KSPA on undirected graph

---

EDIT: apparently I clicked on a link, because I thought I was answering to a new question; ignore this if - as is very likely - this question isn't important to you anymore.

---

Given the restricted version of the problem you're dealing with, this becomes a lot simpler to implement. The most important thing to notice is that in trees, shortest paths are the only paths between two nodes. So what you do is solve all pairs shortest paths, which is O(n²) in trees by doing n BFS traversals, and then you get the k minimal values. This probably can be optimized in some way, but the naive approach to do that is sort the O(n²) distances in O(n² log n) time and take the k smallest values; with some book keeping, you can keep track of which distance corresponds to which path without time complexity overhead. This will give you better complexity than using a KSPA algorithm for O(n²) possible s-t-pairs.

---

If what you actually meant is fixing a source and get the k nodes with the smallest distance from that source, one BFS will do. In case you meant fixing both source and target, one BFS is enough as well.

---

I don't see how you can use the fact that all edges going from a node to the nodes in the level below have the same weight without knowing more about the structure of the tree.