加權圖中的顯示路徑

我有一個加權圖。我已經爲圖中的每個節點分配了三個密鑰。我想要一個代碼，如果圖中有兩個唯一節點，它將顯示所有連接兩個節點是否存在公共密鑰。節點也可以以多跳方式連接。加權圖中的顯示路徑

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節點的數量。如果我想找到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）被連接。

用戶在圖形中輸入連接。密鑰池中的數字是隨機生成的。分配給節點1的密鑰是5,3,1和節點5 7,10,7。這兩個節點沒有公共密鑰。因此不應打印此路徑。如果公共密鑰從所述源（節點1）存在的路線應運行到目的地（節點5）

來源

2013-03-03 Annie Sharon

如果你_want_代碼，你應該寫一些。如果你有更具體的問題，或者你被困在某個地方，請說明你迄今爲止做了什麼。 – 2013-03-03 17:30:30

直到現在我形成了使用權重的矩陣。並從這個矩陣中找出圖中兩個節點之間的路徑。我不知道如何僅在兩個節點之間存在公共密鑰時才找到路徑。 – 2013-03-03 17:36:21

這是一個好的開始，你應該發佈它（問題內部），以便那些試圖回答你的問題的人有一些工作。此外，一個全面的例子將有助於理解你在做什麼。 – 2013-03-03 17:41:12

可以向下把問題分解成兩個步驟：

確定哪些節點連接和共享相同的密鑰。該信息將存儲在矩陣中（我們用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的矢量化操作可以真正幫助使代碼更高效，更優雅！

來源

2013-03-03 19:51:33

非常感謝。 – 2013-03-04 17:19:31

加權圖中的顯示路徑

回答

相關問題