1

我对 MATLAB 相当陌生，并且有一段代码可以创建距离矩阵。更准确地说，它在无向图上的点之间创建距离矩阵 D，使得 Dij 是该图上点之间的最短路径。这个矩阵显然是对称的（因为图是无向的），下面是我用来创建它的代码片段：

D = zeros(size(data,1));
for i = 1:size(data, 1)
    for j = 1:size(data, 1)
        [D(i, j), ~, ~] = graphshortestpath(G, i, j, 'Directed', false);
    end
end

这显然是非常浪费的，因为我没有利用矩阵的对称性。有什么方法可以只计算矩阵的上三角部分，然后以某种方式将下三角部分“附加”到它，这样我就可以将计算从 n^2 减少到 n^2 / 2？

任何帮助表示赞赏，

杰森

4

3 回答 3

2

当然。想想迭代的顺序，找出首先到达哪个三角形。

D = zeros(size(data,1));
for i = 1:size(data, 1)
    for j = 1:size(data, 1)
        if j > i
            [D(i, j), ~, ~] = graphshortestpath(G, i, j, 'Directed', false);
        else
            D(i, j) = D(j, i);
        end
    end
end

如果对角线元素不完全为零，则可以if j >= i改用。

于 2013-04-16T03:59:36.997 回答
1

对于无向和无权图，计算距离矩阵的另一种方法

如果您试图减少运行时间，可能会有所帮助。在 Matlab 的情况下，大多数时候，我发现逐个扫描条目比较慢。我只是猜测你问这个问题的目的，如果我跑题了，对不起。

给定一个邻接矩阵（ G ），我将按以下方式计算距离矩阵，

假设： 1. G 是无向且未加权的（矩阵填充有 '0' 和 '1' ） 2. N 是图的顺序，G 的大小为 N x N

function [D,connect]=genDistance(G,N)

D = G;
B = G;
connect = 0;
i=1;
while((~connect)&&(i<N-1))    % the maximum distance from one vert to another
    i = i + 1;                % is N-1
    B = B * G;                % G to the power of i
    D = D + i * (D==0&B>0);   % D==0 & B>0 the entries to be updated 
    connect = ( min(min(D)) )>0;  %check if D has zero entry
end
D ( eye(N) ) = 0 ; %clear diagonal entries
  • (i,j) "G power k" 中的条目将为您提供 G 中从 Vi 到 Vj 的长度为 k 的步行次数
  • 最后 connect 会告诉你图是否连通
于 2013-04-16T08:02:57.557 回答
0

G您可以为矩阵的下部生成索引

N = length(G);
[irow, icol] = find(tril(ones(N),-1));

然后你可以遍历这些索引：

D = zeros(size(G));
for i = 1:numel(irow)
   [D(irow(i), icol(i)] = graphshortestpath(G, irow(i), icol(i), 'Directed', false);
end
D = D + D';

另一种选择是使用带有这些索引的 ARRAYFUN 和 SQUAREFORM 将结果向量转换为方阵：

D = arrayfun(@(x,y) graphshortestpath(G,x,y, 'Directed', false), irow, icol);
D = squareform(D);
于 2013-04-16T04:05:54.483 回答