At Percona’s web store you can order your MySQL database support needs in minutes. No hassles, no fuss, just pick and click. Pay online with a credit card.

Become a Premium Member and unlock a new, free course in leading technologies each month.

Solved

Posted on 2012-03-16

hello all, I want to find an algorithm that finds all possible path lengths from the other nodes to specifically node 1in the network. I already know about dijkstra's algorithm for finding the shortest path length, what I need is an algorithm that tells me all the possible paths that can be taken without going through the same node more than once for each path, I have attached a picture of my network just to give you a visual of what am working with. can anyone help me

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

- Help others & share knowledge
- Earn cash & points
- Learn & ask questions

2 Comments

The recursive part would go like this, start at node 1 and find all possible adjoining nodes, then for each node found, recursively do just the same, ie. find all possible adjoining nodes of each node (except for the previously visited nodes in that path). The recursions terminating condition is when it visits a node where all possible adjoining nodes have already been visited. The paths found at the terminating conditions, and all intermediate paths are all solutions to what you are after. Note, that this will grow large with even a small number of nodes.

(a) Remove an edge and calculate all paths in smaller graph.

(a) Replace edge and work out other paths formed that contained the replaced edge.

I don't think this is that hard,

(c) Apply recursively.

If

(This has a dynamic programming smell about it, else it is insanely non-polynomial.)

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Earn Certification

HTML5 Specialist - Certification

Free withPremium

Course of the Month5 days, 3 hours left to enroll

Earn Certification

Lean Six Sigma Yellow Belt

$99.00$89.10

Join the community of 500,000 technology professionals and ask your questions.