You are now following this question
- You will see updates in your followed content feed.
- You may receive emails, depending on your communication preferences.
How can I find all possible paths between 2 arbitrary nodes in both acyclic and cyclic directed graph?
4 views (last 30 days)
Show older comments
How can I find all possible paths between 2 arbitrary nodes in both acyclic and cyclic directed graph?
Answers (1)
Walter Roberson
on 17 Jun 2013
There are potentially (and usually) an infinite number of paths between two arbitrary nodes on cyclic graphs.
15 Comments
Hoda
on 17 Jun 2013
What about acyclic directed graph?How can I find all possible paths between 2 arbitrary nodes in acyclic directed graph?
Hoda
on 3 Jul 2013
I can't use Dijkstra and the A* algorithms,because, weight matrix in not constant,and i have to find all possible path between 2 nodes,do u know any algorithms that i can use? As I understood ,we can use dbs or bfs;but i don't know how?
Walter Roberson
on 3 Jul 2013
Are you saying that the connectivity (not distance per se) between the nodes varies with time, and given the time-evolving information you need to find all possible paths between two nodes from a given start time? Or are you saying that the connectivity stays the same but the distances vary with time and you need to find not just all the possible paths but also the total distances they would have taken, taking into account that the change in distances is happening while the travel between nodes is going on?
Sounds something like asking "Suppose you leave for work at 8:0 AM and given that the traffic will vary like {this}, figure out all the different timings it could have taken, not just the best route you could have taken."
Hoda
on 3 Jul 2013
let me explain the problem in an other way Imagine that we want to have all paths from node 20 to node 1;and the paths are such: 20-10-9-8-3-2-1; 20-10-9-3-2-1; 20-10-4-3-2-1; In my problem,a node's coordinates depends on last connected node,eg coordinates of node 3 in first path,differs with in second and third path,because in first path ,previous node of 3 is 8 and in second is 9 and in third is 4, so can dikjstra solve this problem? I think ,because the node's coordinate depend on previous node,it is better to have all path, then calculate the cost and find out the minimum one.,Accordingly, the question is that how we can find all possible paths between 2 arbitrary nodes in a directed graph?
Walter Roberson
on 3 Jul 2013
Is there a difference between what you write, compared to saying that the distance from 8 to 3 is one value and from 9 to 3 a second value, and from 4 to 3 is a third value? Once you are at node 3 and headed to node 2, does the distance between 3 and 2 depend on where you came from before node 3?
Calculating all paths and finding the minimum is not necessarily required. If you have already found a path of length (say) 18, and you are currently at a node having gotten there in (say) 15, but all paths out of the node are cost greater than 3, then there is no point in trying any of the paths, because you know that none of them can have a result shorter than the known best path. This is, if I recall, a difference between dijkstra and A*, that A* prunes like this where dijkstra does not.
Hoda
on 3 Jul 2013
Exactly,I mean distance between 3 and 2 depends on where I came from before node 3? 8,9 or 4? As u know dijkstra has a recursive process,I am not sure does it consider the above condition or not? So ,What is the solution in ur opinion?
Walter Roberson
on 3 Jul 2013
How many steps back need to be taken into account to know the distance to a potential next node? Is it the number of previous nodes that is important in determining following distances? Is it the distance already traveled that determines how the following distances get modified? Do the distances to the potential next nodes change in a consistent way, such as all the potential next distances get multiplied by (1 + alpha) for some constant alpha? If not, can the modification to the distances be represented in terms of a matrix multiplication ?
If it happens to be the case that the original distances matrix is D, and there is a matrix M such that after one step the distances are D*M, and after two steps the distances are D*M*M and so on, D*M^t after t steps, then this can be easily handled with a trivial modification to the dijkstra algorithm.
What is it that you are modelling, that the potential next distances are modified according to the route taken to get to that point ?
Hoda
on 4 Jul 2013
The main problem is in raster enviroment that I converted the pixels to nodes and their neighbourhood shows the edges,so we will have a directed acyclic graph,the issue is that if i want to go from node 10 to 4,i should have midpoint of (10,4),this midpoint is node 4 coordinate while it's previous node is 10.Accordingly ,If we want to use dikjstra,calculating the weight matrix along with finding the path is simultaneously,I cann't determine weight matrix prior of starting algorithm.The cost is not just distance ,it is distance plus angle between 2 adjacency nodes (adjacency pixels in raster enviroment).
Walter Roberson
on 4 Jul 2013
You need to post an example diagram. http://www.mathworks.com/matlabcentral/answers/7924-where-can-i-upload-images-and-files-for-use-on-matlab-answers
NG
on 5 Jan 2017
I am guessing that Hoda's question was about simple paths (without repeating vertices). Although there may be many such paths (but finitely many) it is still surprising that there are no such Matlab routines out there.
Walter Roberson
on 5 Jan 2017
No, Hoda indicated,
"Exactly,I mean distance between 3 and 2 depends on where I came from before node 3?"
which is not a simple path problem.
There are routines to find all the acyclic paths between two nodes when the distance matrix does not change in time or according to where you came from.
See Also
Categories
Find more on Construction in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!An Error Occurred
Unable to complete the action because of changes made to the page. Reload the page to see its updated state.
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)
Asia Pacific
- Australia (English)
- India (English)
- New Zealand (English)
- 中国
- 日本Japanese (日本語)
- 한국Korean (한국어)