Solved

All possible path in a network

Posted on 2012-03-16
2
424 Views
Last Modified: 2012-03-24
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 meA sample of the network graphA sample of the network graph
0
Comment
Question by:cowboy22
2 Comments
 
LVL 35

Assisted Solution

by:mccarl
mccarl earned 150 total points
Comment Utility
The easiest way would probably be a recursive algorithm. Just go in reverse though. Start at node 1, and find the all possible paths that don't visit nodes twice. And then reverse these paths gives you all possible paths from all nodes back to node 1.

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.
0
 
LVL 31

Accepted Solution

by:
GwynforWeb earned 160 total points
Comment Utility
Recursive algorithm

(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, (see below).
(c) Apply recursively.


If n is the chosen node for all paths to, and uv is removed edge. The the extra paths after replacement are formed by patching all sections of the u to n paths that do not have a vertex in common with a v to n path. Then repeat the other way around.
(This has a dynamic programming smell about it, else it is insanely non-polynomial.)
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
Exam question 48 99
Triangles - computing angles 6 39
Homework Help 5 48
Calculating Standard Deviation inside Excel. 5 50
Complex Numbers are funny things.  Many people have a basic understanding of them, some a more advanced.  The confusion usually arises when that pesky i (or j for Electrical Engineers) appears and understanding the meaning of a square root of a nega…
Article by: Nadia
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
This video discusses moving either the default database or any database to a new volume.
Illustrator's Shape Builder tool will let you combine shapes visually and interactively. This video shows the Mac version, but the tool works the same way in Windows. To follow along with this video, you can draw your own shapes or download the file…

743 members asked questions and received personalized solutions in the past 7 days.

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

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now