Solved

All possible path in a network

Posted on 2012-03-16
2
429 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
[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
  • Learn & ask questions
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

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Introduction On a scale of 1 to 10, how would you rate our Product? Many of us have answered that question time and time again. But only a few of us have had the pleasure of receiving a stack of the filled out surveys and being asked to do somethi…
Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
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.
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

751 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