1

私はMATLABを初めて使用し、距離行列を作成するコードを持っています。より正確には、Dij がそのグラフ上の点間の最短経路となるように、無向グラフ上の点間の距離行列 D を作成します。この行列は明らかに対称的です (グラフは無向であるため)。次のコード スニペットを使用して作成します。

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 に答える
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';

もう 1 つのオプションは、ARRAYFUN をこれらのインデックスで使用し、SQUAREFORM を使用して、結果のベクトルを正方行列に変換することです。

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