Let's say I have a graph with $N$ nodes, $A$ arcs and an average branching factor $b$. I want to find the $K$ shortest paths between two nodes.

Is there some relation (even approximate is fine) that expresses the dependency between the parameter $K$ and percentage of nodes included in the paths discovered by running the algorithm (Yen's loopless KSP)?

For example, in a graph of 20 nodes, the ($1st$) shortest path from node $1$ to $12$ is $1-4-7-12$, while the $2nd$ shortest path is $1-4-6-9-12$.

So for $K=1$, the discovered path contains $4/20 = 20\%$ of the nodes in the graph. For $K=2$, the two paths contain $6/20 = 30\%$ of the nodes. This relation between $K$ and the percentage is what I'm looking for.

  • 1
    $\begingroup$ "by running the algorithm" - which algorithm are you planning to use? Also, what are your thoughts? What have you tried, and where did you get stuck? $\endgroup$
    – D.W.
    Aug 29 '16 at 1:25
  • $\begingroup$ Since even Dijkstra et al. always "explore" all nodes -- and they have to! -- I think it's unlikely that a k-shortest-paths algorithm can make do with less. $\endgroup$
    – Raphael
    Aug 29 '16 at 2:03
  • $\begingroup$ @Raphael: anyway, the question makes a lot of sense in the average case. I mean, there is certainly a relationship between the number of shortest paths to compute and the extra amount of work to do. I think we know nothing about this and the answer might depend on parameters other than those mentioned in the question. Anyway, devil0150 I would strongly recommend you to edit your question and to post the question as a relationship between $K$ and the extra amount of work (which actually involves re-expansions instead of generations!) $\endgroup$ Aug 29 '16 at 11:36
  • 1
    $\begingroup$ What is a branching factor of a graph? I know what a branching factor in a tree is, but I don't know what does it mean in a generic graph! $\endgroup$
    – orezvani
    Sep 1 '16 at 2:06

It seems to me the relation depends purely on how the graph is made. Think about a cycle. The shortest path between two adjacent vertices contains 2 vertices while the second contains n vertices


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.