從起始節點到結束節點的所有可能路徑

Question

我有一個帶有用戶定義的節點數'n'的加權圖。我想要一個代碼，給定圖中的兩個獨特節點，它將顯示連接兩個節點的所有路徑節點。 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  

基質重量表示任意兩個給定的節點之間的連接。這意味着節點（1,2）（1,3）（3,4）（4,3）被連接。

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 

這是我寫的代碼，用於查找從源到目標的可能路徑。 'p'矩陣保存從源到目的地的最終路徑。 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. 

如果我給我的輸入源爲3和目的地1中的代碼無法正常工作。

Answer 1

下面是一個更好的矢量化的方法（我假設你不能跨越同一個節點兩次）。你想盡可能地減少嵌套for循環。儘可能使用矢量和矩陣操作。

這個想法是建立一個所有路徑的列表，並同時將所有可能的下一個節點添加到列表中的每個元素上。 該函數返回一個Mx2單元陣列，其中M是最長的（大多數節點訪問的）路徑。 第一列中的每個單元格都包含一個矩陣，其中每一行都是長度爲i的不同路徑。第二列中的每個單元格包含一個列向量以及每個路徑的相應成本。

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 

編輯：添加如何打印路徑