distances

すべてのノード ペアの最短経路の距離

構文

d = distances(G)

d = distances(G,s)

d = distances(G,s,t)

d = distances(___,'Method',algorithm)

説明

d = distances(G) は行列 d を返します。ここで、d(i,j) はノード i とノード j の間の最短経路の距離です。グラフが重み付きの場合 (つまり、G.Edges が変数 Weight を含む)、これらの重みはグラフ エッジの距離として使用されます。それ以外の場合、すべてのエッジの距離は 1 と見なされます。

d = distances(G,s) は、ソース ノードを s で定義されたノードに制限します。これにより、d(i,j) はノード s(i) からノード j までの距離になります。

d = distances(G,s,t) はさらに、ターゲット ノードを t で定義されたノードに制限します。これにより、d(i,j) はノード s(i) からノード t(j) までの距離になります。

d = distances(___,'Method',algorithm) は、前述の構文に示した任意の入力引数を使用して最短経路を計算するときに、使用するアルゴリズムをオプションで指定します。たとえば、G が重み付きグラフの場合、distances(G,'Method','unweighted') は G のエッジの重みを無視し、すべてのエッジの重みを 1 として扱います。

例

すべてのノード ペアの最短経路の距離

グラフを作成してプロットします。

s = [1 1 1 2 5 5 5 8 9];
t = [2 3 4 5 6 7 8 9 10];
G = graph(s,t);
plot(G)

グラフ内のすべてのノード ペアについて、ノード間の最短経路の距離を計算します。グラフ エッジには重みがないので、すべてのエッジの距離は 1 と見なされます。

d = distances(G)

d = 10×10

     0     1     1     1     2     3     3     3     4     5
     1     0     2     2     1     2     2     2     3     4
     1     2     0     2     3     4     4     4     5     6
     1     2     2     0     3     4     4     4     5     6
     2     1     3     3     0     1     1     1     2     3
     3     2     4     4     1     0     2     2     3     4
     3     2     4     4     1     2     0     2     3     4
     3     2     4     4     1     2     2     0     1     2
     4     3     5     5     2     3     3     1     0     1
     5     4     6     6     3     4     4     2     1     0

G は無向グラフであるため、d は対称です。一般的に d(i,j) はノード i とノード j の間の最短経路の長さであり、無向グラフの場合、これは d(j,i) と等価です。

たとえば、ノード 1 とノード 10 の間の最短経路の長さを求めます。

d(1,10)

ans = 
5

指定ソースからの最短経路の距離

グラフを作成してプロットします。

s = [1 1 1 1 2 2 3 4 4 5 6];
t = [2 3 4 5 3 6 6 5 7 7 7];
G = graph(s,t);
plot(G)

ノード 1、ノード 2 およびノード 3 から、グラフにあるその他すべてのノードまで最短経路の距離を求めます。

d = distances(G,[1 2 3])

d = 3×7

     0     1     1     1     1     2     2
     1     0     1     2     2     1     2
     1     1     0     2     2     1     2

d を使用して、ノード 1 からノード 7 までの最短経路の距離を求めます。

d(1,7)

ans = 
2

指定ターゲットまでの最短経路の距離

グラフを作成してプロットします。

s = [1 1 1 2 2 3 3 4 5 5 6 7 8  8 10 11];
t = [2 3 10 4 12 5 4 6 6 7 9 8 9 11 11 12];
G = graph(s,t);
plot(G)

ノード 5 および 7 からノード 2 および 3 までの最短経路の距離を求めます。

sources = [5 7];
targets = [2 3];
d = distances(G,sources,targets)

d = 2×2

     3     1
     4     2

d を使用して、ノード 7 とノード 3 の間の最短経路の距離を求めます。この場合、d(i,j) はノード sources(i) からノード targets(j) までの距離です。

d(2,2)

ans = 
2

エッジの重みを無視

重み付きエッジをもつ有向グラフを作成し、プロットします。

s = [1 1 1 2 5 3 6 4 7 8 8 8];
t = [2 3 4 5 3 6 4 7 2 6 7 5];
weights = [100 10 10 10 10 20 10 30 50 10 70 10];
G = digraph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight)

グラフ ノードのすべてのペアについて、ノード間の最短経路の距離を求めます。

d = distances(G)

d = 8×8

     0    90    10    10   100    30    40   Inf
   Inf     0    20    50    10    40    80   Inf
   Inf   110     0    30   120    20    60   Inf
   Inf    80   100     0    90   120    30   Inf
   Inf   120    10    40     0    30    70   Inf
   Inf    90   110    10   100     0    40   Inf
   Inf    50    70   100    60    90     0   Inf
   Inf   100    20    20    10    10    50     0

G は有向グラフであるため、d は非対称であり、d(i,j) はノード i とノード j の間の距離に対応します。d の Inf 値は到達できないノードに対応します。たとえば、ノード 1 には先行ノードがないので、グラフ内のその他すべてのノードからノード 1 に到達することはできません。したがって、d の最初の列には、ノード 1 に到達できないことを示す Inf 値が多数含まれます。

既定で、distances はエッジの重みを使用して距離を計算します。'Method' を 'unweighted' に指定して、エッジの重みを無視し、すべてのエッジの距離を 1 として扱います。

d1 = distances(G,'Method','unweighted')

d1 = 8×8

     0     1     1     1     2     2     2   Inf
   Inf     0     2     4     1     3     5   Inf
   Inf     4     0     2     5     1     3   Inf
   Inf     2     4     0     3     5     1   Inf
   Inf     5     1     3     0     2     4   Inf
   Inf     3     5     1     4     0     2   Inf
   Inf     1     3     5     2     4     0   Inf
   Inf     2     2     2     1     1     1     0

入力引数

G — 入力グラフ

graph オブジェクト | digraph オブジェクト

入力グラフ。graph オブジェクトまたは digraph オブジェクトとして指定します。無向グラフの作成には graph を、有向グラフの作成には digraph を使用します。

例: G = graph(1,2)

例: G = digraph([1 2],[2 3])

s — ソース ノード

'all' (既定値) | ノード インデックス | ノード名

ソース ノード。1 つ以上のノード インデックスまたはノード名を指定するか、'all' を指定してすべてのソース ノードを選択します。

次の表に、1 つ以上のノードを数値ノード インデックスまたはノード名のいずれかで参照するさまざまな方法を示します。

形式	単一ノード	複数ノード
ノード インデックス	スカラー 例: 1	ベクトル 例: [1 2 3]
ノード名	文字ベクトル 例: 'A'	文字ベクトルの cell 配列 例: {'A' 'B' 'C'}
	string スカラー 例: "A"	string 配列 例: ["A" "B" "C"]

s と t は、名前が 'all' または 'Method' であるノードを指定してはなりません。これらのノード名はオプション名と競合しています。このような場合には、代わりに findnode を使用してノード インデックスを渡します。

例: distances(G,[1 2])

例: distances(G,'all',[1 3 5])

t — ターゲット ノード

'all' (既定値) | ノード インデックス | ノード名

ターゲット ノード。1 つ以上のノード インデックスまたはノード名を指定するか、'all' を指定してすべてのターゲット ノードを選択します。

s と t は、名前が 'all' または 'Method' であるノードを指定してはなりません。これらのノード名はオプション名と競合しています。このような場合には、代わりに findnode を使用してノード インデックスを渡します。

例: distances(G,[1 2])

例: distances(G,'all',[1 3 5])

algorithm — 最短経路アルゴリズム

'auto' (既定値) | 'unweighted' | 'positive' | 'mixed'

最短経路アルゴリズム。次の表のいずれかのオプションとして指定します。

オプション	説明
'auto' (既定)	'auto' オプションを設定すると、自動的にアルゴリズムが選択されます。 'unweighted' は、エッジの重みをもたない graph および digraph の入力に対して使用されます。 'positive' はエッジの重みをもつすべての graph の入力に対して使用され、重みは非負の数であることが求められます。このオプションは、エッジの重みが非負である digraph の入力に対しても使用されます。 'mixed' は、一部のエッジの重みに負数が含まれる digraph の入力に対して使用されます。グラフは負の循環をもつことができません。
'unweighted'	幅優先検索。すべてのエッジの重みを 1 として扱います。
'positive'	ダイクストラ アルゴリズム。すべてのエッジの重みが非負の数でなければなりません。
'mixed' (digraph 専用)	有向グラフのベルマン・フォード アルゴリズム。グラフに負の循環があってはなりません。 同じ問題について 'mixed' の処理速度は 'positive' よりも遅くなりますが、'mixed' は一部のエッジに負の重みを使用できるので、より柔軟です。

メモ

多くのグラフについて、'unweighted' が最速のアルゴリズムであり、次に 'positive'、'mixed' の順になっています。

例: distances(G,s,t,'Method','unweighted')

出力引数

d — ノード ペア間の最短経路の距離

行列

ノード ペア間の最短経路の距離。行列として返されます。d のサイズは、(ソース ノード数) 行 (ターゲット ノード数) 列です。Inf 値は経路が存在しないことを示します。

ヒント

• 関数 shortestpath、shortestpathtree および distances は、負のエッジの重みをもつ無向グラフ、より一般的には負の循環をもつグラフをサポートしません。その理由は次のとおりです。

  • "負の循環" とは、あるノードからそのノード自身に戻る経路であり、その経路のエッジの重みの合計が負になるものです。2 つのノード間に負の循環がある場合、それらのノード間に最短経路は存在しません。これは、短い経路は常に負の循環を通過することにより検出されるからです。

  • 無向グラフ内に負のエッジの重みが 1 つあると、負の循環が作成されます。

拡張機能

スレッドベースの環境
MATLAB® の backgroundPool を使用してバックグラウンドでコードを実行するか、Parallel Computing Toolbox™ の ThreadPool を使用してコードを高速化します。

バージョン履歴

R2015b で導入

参考

shortestpathtree | shortestpath | nearest | graph | digraph