Find All Possible Paths from a Single SourceNode to a Single TargetNode Without Visiting Old Paths

3 次查看（过去 30 天）
czeslaw
czeslaw 2018-1-29
编辑： czeslaw 2018-1-29
Hi All,
If I have node set nodeset=[nodeID x y] of size numberOfNodes x 3. I also have undirected path pathset=[PathID nodeID1 nodeID2] of size PathID x 3. I would like to find all possible paths from a single sourceNode to a single TargetNode. Visiting the previously travelled edge (path) is not allowed because there would be too much solutions. Visiting the previously travelled vertices are allowed.
Is there a function out there in Matlab that can help me do this: Example: AllPaths(nodeset, pathset, sourceNode, TargetNode) output: sets of vector containing PathID's that gives those possible path.
Your help much appreciated. Thank you in advance.
  2 个评论
Walter Roberson
Walter Roberson 2018-1-29
On undirected graphs, there are an infinite number of paths between any two nodes that are connected indirectly at all.
Someone asked a similar question a couple of months ago; they were trying to investigate centrality of social networks. I was not able to come up with an algorithm which did not come down to breadth-first search or depth-first search.
Steven Lord
Steven Lord 2018-1-29
If like the person Walter remembers who asked the similar question a couple months ago you're trying to investigate centrality of a graph or digraph, take a look at the centrality function.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（1 个）

czeslaw
czeslaw 2018-1-29
编辑：Walter Roberson 2018-1-29
Thank you all for the reply,
In response to Walter, for instance, if I have paths following a square figure with a diagonal in the middle, there will be 3 ways to go from point A to points C.
So if I input AllPaths(nodeset, pathset, A, C), the function that I looked for should output:
1. A B C
2. A C
3. A D C
https://www.google.com/search?q=square+with+diagonal+in+middle&source=lnms&tbm=isch&sa=X&ved=0ahUKEwitqbmr4_3YAhWb8oMKHQW7DHYQ_AUICigB#imgrc=b7rkz9Th23mF7M:
I am not certain about that centrality function, would it be helpful for this kind of example. Any suggestions would be much appreciated. Thank you.
  6 个评论
显示 4更早的评论
czeslaw
czeslaw 2018-1-29
编辑：czeslaw 2018-1-29
Hi Roberson, thanks for the reply.
Based on your figure, I can see that ABC and ABDEBC are allowed. I do not see how ADEDBC is possible here since there are no path between A D in that figure? In any case, Its okay to visit the previously visited vertex, but not allowed to visit the previously visited edge (connectivity between two vertices). The later case I imagine would result in extremely huge number of solutions. The former (able to visit the previously travelled vertex but not path) would have fewer solutions. But if both cases are difficult, not able to visit travelled vertices and paths (edges) would also work for me, in this case, only ABC is the solutions as you mentioned.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by