K shortest paths - any relation between K and % of graph nodes in discovered paths?
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