0

我有一个带有用户定义的节点数'n'的加权图。我想要一个代码，给定图中的两个唯一节点，它将显示连接这两个节点的所有路径。 图表示例

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 显示任意两个给定节点之间的连接。这意味着节点 (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

这是一种更好的矢量化方法（我假设您不能两次穿过同一个节点）。您希望尽可能减少嵌套的 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

编辑：添加了如何打印路径

于 2013-03-20T23:58:21.237 回答