Solved

All possible path in a network

Posted on 2012-03-16
2
427 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
ID: 37729265
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
ID: 37732774
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

Gigs: Get Your Project Delivered by an Expert

Select from 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.

Question has a verified solution.

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

How to Win a Jar of Candy Corn: A Scientific Approach! I love mathematics. If you love mathematics also, you may enjoy this tip on how to use math to win your own jar of candy corn and to impress your friends. As I said, I love math, but I gu…
Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…

813 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

18 Experts available now in Live!

Get 1:1 Help Now