Enumerate first 2^20 paths which don't include cycles between two vertixes

Question

Input is an undirected, cyclic, planar graph, with each vertex having at most 8 edges.

What is the way to enumerate over all paths betwen two vertexes v_0, v_1 in an order from shortest to longest? What is computational complexity?

If above is not possible, what is a way to generate all paths of length not longer than K.

Answer 1

You want to get the shortest path to the longest path -> indicates you can try BFS.

The path can't include the cycle -> you should storage the path have passed what vertices(when you do BFS).

The complexity: you can see the path don't include the cycle means the path can pass every node only one times. So the solution space is O(n!) and BFS may visit every path in the solution space in the worst case. So the complexity is O(n!).

You may be disappointed with that result. Okay, your problem is a famous problem that have been well studied. You can read this paper:

Finding the K Shortest Loopless Paths in a Network
Jin Y. Yen

Or the wikipedia pages for a intuitive view for the K-th shortest path problems.