0

我有一个加权图。我为图中的每个节点分配了三个键。我想要一个代码，给定图中的两个唯一节点，如果存在公共键，它将显示连接两个节点的所有路径。节点也可以以多跳方式连接。

keypool = randint(n,n,[1,10]) %key pool generation
for l = 1:n
for k = 1:3
    nodekey(l,k) = keypool(l,k);%Selects key from key pool
end;
end;
for i=1:n
fprintf('%s %d \t =  %d  %d  %d \n','key_node',i,nodekey(i,:));
end

这是我为生成所有节点的随机密钥而编写的代码。只有当有一个公共密钥时，我才知道如何找到两个节点之间的路径。输入节点数：5

keypool =

 5     3     1     7     7
 3     7     8     4     3
 9     3    10     7    10
 2     5     2     7     8
 7    10     7     3     5

key_node 1   =  5  3  1 
key_node 2   =  3  7  8 
key_node 3   =  9  3  10 
key_node 4   =  2  5  2 
key_node 5   =  7  10  7

n 的值是用户输入的节点数。上面的代码将为五个节点生成这样的随机密钥。如果我想找到 node1 和 node5 之间的路径，假设可能的路径是：1->2->3->5、1->5、1->2->5。应该打印仅具有公共密钥的路径。即 1->2->3->5, 1->2->5。

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) 已连接。

用户在图中输入连接性。密钥池中的数字是随机生成的。分配给 node1 的键是 5,3,1 和 node5 7,10,7。这两个节点没有公共密钥。因此不应打印此路径。如果源 (node1) 存在公共密钥，则应将路由遍历到目标 (node 5)

4

1 回答 1

1

您可以将问题分解为两个步骤：

  1. 确定哪些节点已连接并共享相同的密钥。此信息将存储在一个矩阵中（我们用 表示M），我将其称为修改后的邻接矩阵。

  2. 根据修改后的邻接矩阵查找从一个节点到另一个节点的所有可能路径。

第一部分可以这样解决：

%// Obtain matrix 'sh' where each element at position (i, j) indicates if
%// node i and node j share a key
pairs = nchoosek(1:n, 2);                %// All possible pairs of nodes
sh = zeros(n);
for k = 1:size(pairs, 1)
    node1 = pairs(k, 1);
    node2 = pairs(k, 2);
    sh(node1, node2) = any(ismember(nodekey(node1, :), nodekey(node2, :)));
    sh(node2, node1) = sh(node1, node2); %// Matrix must be symmetrical
end

%// Obtain the modified adjacency matrix
M = sh & (wt > 0);

我会把第二部分留给你。使用给定的（修改的）邻接矩阵找到从节点 A 到节点 B 的所有可能路径M是一个众所周知的问题。这是它的一种可能实现的链接。

希望这可以帮助！

PS：您可以通过编写
来简化生成：nodekey

nodekey = keypool(:, 1:3);

MATLAB 的向量化操作确实可以帮助使代码更加高效和优雅！

于 2013-03-03T19:51:33.113 回答