Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

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

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

Course of the Month4 days, 5 hours left to enroll

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