Finding Possible Paths between two nodes

조회 수: 3 (최근 30일)
Rawan Alghamdi
Rawan Alghamdi 2018년 7월 23일
댓글: Christine Tobler 2018년 8월 9일
Hello, I am trying to find all "possible" paths between two nodes, in an n*n matrix, where n is the number of nodes. Basically, I have this matrix (n*n) which defines a connection between nodes if its value is non zero (the value represents the weight of the edge) , and there isn't a connection if the value is zero. The restriction of making a path "possible": 1) the nodes have to be connected. 2) in each path, a node must not be visited more than once. 3) in each path, an edge must not be visited more than once. 4) the number of hops in the path must be less or equal to (n-1)
Finally I would store all the possible paths in another matrix(num of possible path *n) where it would have its row representing the paths, and if path has number of hops less than (n-1) the rest of the row would be zeros
Below is an example of how the initial matrix of the connections looks like:
A= [
0 0 0 52.6751 57.8655 96.4418 0 94.5074 90.5029 104.3699
0 0 49.8587 0 85.2586 84.3756 0 59.4121 0 0
0 49.8587 0 0 90.3530 119.4477 0 50.8899 0 0
52.6751 0 0 0 97.6427 104.8545 0 0 117.1408 54.3737
57.8655 85.2586 90.3530 97.6427 0 64.1560 0 39.7898 0 0
96.4418 84.3756 119.4477 104.8545 64.1560 0 0 83.9832 0 0
0 0 0 0 0 0 0 0 108.7307 0
94.5074 59.4121 50.8899 0 39.7898 83.9832 0 0 0 0
90.5029 0 0 117.1408 0 0 108.7307 0 0 0
104.3699 0 0 54.3737 0 0 0 0 0 0
];
I have been trying to look to another examples in Matlab Answers and Matlab Exchange in order to help me have an idea of how to create such an algorithm but no code is quite working with me.
Here are some of the links in Matlab that I have tried: https://www.mathworks.com/matlabcentral/answers/171277-how-can-i-get-all-paths-between-two-nodes#answer_165813 https://www.mathworks.com/matlabcentral/answers/293441-how-to-find-all-possible-pathes-between-source-and-destination
P.s: I am testing for number of nodes between (30-90)
  댓글 수: 1
Christine Tobler
Christine Tobler 2018년 8월 9일
Here's a way to do this using the digraph object:
g = digraph(A);
n = numnodes(g);
D = distances(g, 'Method', 'unweighted');
hasPath = isfinite(D);
[src, tgt] = find(hasPath);
Paths = zeros(length(src), n);
for i=1:length(src)
p = shortestpath(g, src(i), tgt(i), 'Method', 'unweighted');
Paths(i, 1:length(p)) = p;
end

댓글을 달려면 로그인하십시오.

답변 (0개)

카테고리

Help CenterFile Exchange에서 Programming에 대해 자세히 알아보기

Community Treasure Hunt

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

Start Hunting!

Translated by