Solved

# All possible path in a network

Posted on 2012-03-16
430 Views
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
0
Question by:cowboy22
[X]
###### Welcome to Experts Exchange

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

LVL 36

Assisted Solution

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

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

Question has a verified solution.

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

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…
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…
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…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…
###### Suggested Courses
Course of the Month5 days, 3 hours left to enroll