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$ – Carlos Linares López 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

