All possible path from starting node to ending node

Question

I have a weighted graph with user defined number of nodes 'n'.I want a code that, given two unique nodes in the graph, that will display all the paths connecting the two nodes . Graph Example

wt=zeros(n,n);
while(1)
i=input('enter the starting node:(0 to quit):');
if (i==0)    
    break;
end
j=input('enter the destination node:');
wt(i,j)=input('Enter the cost: '); 
end
disp('Adjacency Matrix');
for i=1:n
fprintf('           %d',i);
end
for i=1:n
fprintf('\n%d          ',i);
for j=1:n
fprintf('%d          ',wt(i,j));
end
end
Adjacency Matrix
   1           2           3           4           5
1          0          1          1          0          0          
2          0          0          0          0          0          
3          1          0          0          1          0          
4          0          0          1          0          0          
5          0          0          0          0          0     

the matrix wt shows the connection between any two given nodes. this means node (1,2) (1,3) (3,4) (4,3) are connected.

fprintf('\nEnter the source');
s=input(':');
fprintf('\nEnter the destination');
de=input(':');

for i=1:n
m=s;
if(m~=i)
   for j=i:n
    if(m~=j)
        if(M(m,j)>0)
            p(i,j)=j;
            m=j;
        end
    end
    if(p(i,j)==de)
        d(i)=1;
        break;
    end
end
if(d(i)~=1)
    for k=1:j
        p(i,k)=0;
    end
    m=s;
    for k=n : -1 : i
        if(M(m,k)>0)
            p(i,n-k+2)=k;
            m=k;
        end
        if(p(i,n-k+2)==de)
            d(i)=1;
            break;
        end
    end
end
end
end


for i=1:n
j=1;
if(d(i)==1)
    for j=1:n
        if (j==1)
            fprintf('\n path: %d',s);
            kk=s;


        elseif (p(i,j)>0)
            fprintf('->%d',p(i,j));

            plot([nodes(kk, 2) nodes(p(i,j), 2)], [nodes(kk, 3) nodes(p(i,j), 3)], 'k.--')
            kk=p(i,j);
        end
    end
end
fprintf('\t\t hopcount of path %d:  %d',i,count);
count=0;
end

This is the code i have written to find the possible paths from the source to destination. 'p' matrix holds the final path from the source to the destination. OUTPUT:

 enter the starting node:(0 to quit):1
 enter the destination node:2
 Enter the cost: 1
 enter the starting node:(0 to quit):1
 enter the destination node:3
 Enter the cost: 1
 enter the starting node:(0 to quit):2
 enter the destination node:3
 Enter the cost: 1
 enter the starting node:(0 to quit):0

Enter the source:1

Enter the destination:3


     hopcount of path 1:  0
 path 2: 1->2->3         hopcount of path 2:  2
 path 3: 1->3        hopcount of path 3:  1??? 
 Attempt to reference field of      non-structure array.

if i give my input for source as 3 and destination as 1 the code does not work.

Answer 1

Here's a better-vectorized approach (I'm assuming you can't cross the same node twice). You want to minimize your nested for-loops as much as possible. Use vector-and-matrix operations wherever possible.

The idea is to build a list of all the paths and simultaneously add all possible next nodes onto each element in the list. This function returns a Mx2 cell array where M is the longest (most nodes visited) path. Each cell in the first column contains a matrix where every row is a distinct path of length i. Each cell in the second column contains a column vector with the corresponding costs of each path.

function [paths] = allpaths(wt, startnode, endnode)
    lastpath = [startnode]; #We begin with the path containing just the startnode
    costs = [0]; #The cost of this path is zero because we haven't yet crossed any edges
    paths = {zeros(0,1),zeros(0,1)}; #The set of solution paths is empty (I'm assuming startnode!=endnode)
    N = size(wt,1); #Obtain the number of nodes in the graph
    assert(N==size(wt,2)); #Assert that the adjacency matrix is a square matrix
    for i = 2 : N
        #Creates a matrix with a row for each path and a 1 in a column where there's a possible move from the last visited node in a path to this column
        nextmove = wt(lastpath(:, i - 1), :) != 0;

        #Zero out any nodes we've already visited
        d = diag(1:size(lastpath,1));
        nrows = d * ones(size(lastpath));
        inds = sub2ind(size(nextmove), reshape(nrows,[],1), reshape(lastpath,[],1));
        nextmove(inds) = false;

        # If there are no more available moves we're done 
        if nextmove == 0
            break;
        endif

        #For each true entry in our nextmove matrix, create a new path from the old one together with the selected next move
        nextmoverow = d * nextmove;
        nextmovecol = nextmove * diag(1:N);
        rowlist = reshape(nonzeros(nextmoverow),[],1);
        collist = reshape(nonzeros(nextmovecol),[],1);
        nextpath = [lastpath(rowlist,:), collist];

        # Compute the costs of the new set of paths by adding the old ones to the cost of each newly traversed edge
        inds = sub2ind([N,N],nextpath(:, i-1),nextpath(:,i));
        costs = costs(rowlist) + wt(inds);

        # For any path finishing on the end node, add it to the return list (and it's corresponding cost)
        reachedend = nextpath(:,i) == endnode;
        paths = [paths; {nextpath(reachedend, :)},{costs(reachedend)}];

        #Then remove it from the list of paths still being explored
        lastpath = nextpath(~reachedend, :);
        costs = costs(~reachedend);

        #If there are no more paths, we're done
        if isempty(lastpath)
            break;
        endif
    endfor
endfunction


paths = allpaths(wt, startnode, endnode);
for i = 1:size(paths,1)
    mpath = paths{i,1};
    mcost = paths{i,2};
    for j = 1:length(mcost)
        p = mpath(j,:);
        first = true;
        for n = p
            if first
                first = false;
            else
                printf(' -> ');
            endif
            printf('%d', n);
        endfor
        printf('  cost: %d\n',mcost(j));
    endfor
endfor

EDIT: Added how to print the path