MATLAB: Find all the paths between each couple of nodes in a graph

all possible pathsfind path graph

how can I find all the possible paths between each couple of nodes in a graph? Thanks in advance

Best Answer

Create the adjacency matrix and raise it to successive matrix powers.

If the graph is not a directed graph, then there will be an infinite number of possible paths. There might well be an infinite number anyhow.

For example,

A BCD BCD BCD BCD BCD BCD BCD BCD E is a quite plausible path between A and E if A->B, B->C, C->D, D->B and D->E

Perhaps you wanted to ask a slightly different question.

Related Solutions

MATLAB: Coupled Differential Equation

Here is an example where someone is using ode45 to solve an even bigger problem. To avoid out-of-memory errors, make A into a sparse matrix if you can.

EDIT: If I understand your notation, M is actually a vector with components M_q, and ditto for K and B. So you should create a new vector

X = [M; N];

and then define your function as follows:

f = @(x) [-gamma*x(1:end-1) + x(end)*B.*(x(1:end-1)+1) - c*K.*x(1:end-1); P - A*x(end) - x(end)*sum(B.*x(1:end-1))];

(or you could create an easier-to-read function in a separate file).

MATLAB: Shortest Possible Path from All Nodes in a Graph

No, there is no built-in command for that. You could look in the File Exchange.

If you have a vector of source node numbers, s, and a vector of destination (target) node numbers, t, and for any given index K, the distance from node number s(K) to destination t(K) is given by cost c(K), and you only fill in the list in one direction (assume that the backwards links will automatically be filled in by the software), then

maxnode = max([s(:), t(:)]);
sendpaths = cell(maxnode, 1);
G = graph(s, t, c);
for K = 1 : maxnode
 sendpaths{K} = shortestpath(G, K, sinknode);
end

Best Answer

Related Solutions

MATLAB: Coupled Differential Equation

MATLAB: Shortest Possible Path from All Nodes in a Graph

Related Question