0

ユーザー定義のノード数 'n' を持つ加重グラフがあります。グラフ内の 2 つの一意のノードを指定すると、2 つのノードを接続するすべてのパスを表示するコードが必要です。 グラフの例

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

行列 wt は、任意の 2 つのノード間の接続を示します。これは、ノード (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' 行列は、ソースから宛先への最終的なパスを保持します。出力：

 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 を入力すると、コードが機能しません。

4

1 に答える 1

1

これは、より優れたベクトル化されたアプローチです (同じノードを 2 回通過することはできないと想定しています)。ネストされた for ループをできる限り最小限に抑えたい場合。可能な限り、ベクトルと行列の演算を使用してください。

アイデアは、すべてのパスのリストを作成し、同時にリスト内の各要素にすべての可能な次のノードを追加することです。この関数は、Mx2 セル配列を返します。ここで、M は最長の (最も多くのノードが訪問された) パスです。最初の列の各セルには行列が含まれており、各行は長さ i の個別のパスです。2 列目の各セルには、各パスの対応するコストを含む列ベクトルが含まれています。

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

編集：パスを印刷する方法を追加

于 2013-03-20T23:58:21.237 に答える