在加权图中显示路径
在加权图中显示路径
提问于 2013-03-04 00:51:40
我有一个加权的图，我为图中的每个节点分配了三个键，我想要一个代码，在给定图中的两个唯一节点的情况下，如果存在公共键，它将显示连接这两个节点的所有路径。节点也可以以多跳方式连接。
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的值是user.the输入的节点数，上面的代码将为5个节点生成这样的随机密钥。如果我想找到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)是连接的。
用户在密钥池中随机生成的graph.the编号中输入连接性。分配给node1的键是5,3,1，分配给node5的键是7,10,7。这两个节点没有共同的key.Hence。此路径不应打印。如果存在来自源(node1)的公共密钥，则应将路由遍历到目的地(节点5)
回答 1
Stack Overflow用户
回答已采纳
发布于 2013-03-04 03:51:33
您可以将问题分解为两个步骤：
- 确定连接了哪些节点并共享相同的密钥。此信息将存储在一个矩阵(让我们将其表示为
M)中，我将其称为修改后的邻接矩阵。 - 基于修改后的邻接矩阵查找从一个节点到另一个节点的所有可能路径。
第一部分可以这样解决：
%// 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);我会把第二部分留给你。使用给定的(修改的)邻接矩阵M找到从节点A到节点B的所有可能路径是众所周知的问题。下面是它的一个可能实现的a link。
希望这能有所帮助！
P.S:
您可以通过编写以下代码来简化nodekey的生成：
nodekey = keypool(:, 1:3);MATLAB的矢量化操作真的可以让代码变得更高效、更优雅！
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15188035
复制相关文章
相似问题
腾讯云开发者
