5
$\begingroup$

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.

$\endgroup$
4
  • 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, 2016 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, 2016 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$
    – Carlos Linares López
    Aug 29, 2016 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, 2016 at 2:06

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$

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.