How can I find all possible paths between 2 arbitrary nodes in both acyclic and cyclic directed graph?

How can I find all possible paths between 2 arbitrary nodes in both acyclic and cyclic directed graph?

Answer 1

[Walter Roberson]

There are potentially (and usually) an infinite number of paths between two arbitrary nodes on cyclic graphs.

[Hoda]

What about acyclic directed graph?How can I find all possible paths between 2 arbitrary nodes in acyclic directed graph?

[Walter Roberson]

Look into the Dijkstra algorithm and the A* algorithm.

[Hoda]

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]

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]

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]

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]

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]

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]

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]

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

[Hoda]

Is it possible to give me an email ID? I have problem with zip file.

[Walter Roberson]

If you click on my name, it will show you my email address.

[Hoda]

tnx ,I sent the file;subject is:my matlab problem

[NG]

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]

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.