shortestpathtree

ノードからの最短経路木

構文

TR = shortestpathtree(G,s)

TR = shortestpathtree(G,s,t)

TR = shortestpathtree(___,Name,Value)

[TR,D] = shortestpathtree(___)

[TR,D,E] = shortestpathtree(___)

説明

TR = shortestpathtree(G,s) は、ソース ノード s からグラフ内のその他すべてのノードまでの最短経路からなる木を含む有向グラフ TR を返します。グラフが重み付きの場合 (つまり、G.Edges が変数 Weight を含む)、これらの重みはグラフ エッジの距離として使用されます。それ以外の場合、すべてのエッジの距離は 1 と見なされます。

TR = shortestpathtree(G,s,t) は、複数のソース ノードまたはターゲット ノード間の最短経路からなる木を計算します。

• s を単一のソース ノードにして、t に複数のターゲット ノードを指定できます。

• s に複数のソース ノードを指定して、t に単一のターゲット ノードを指定できます。

TR = shortestpathtree(___,Name,Value) は、前述の構文にある任意の入力引数を組み合わせて、1 つ以上の名前と値のペアの引数で指定される追加のオプションを使用します。たとえば、shortestpathtree(G,s,'OutputForm','vector') は最短経路木を表す数値ベクトルを返します。

[TR,D] = shortestpathtree(___) はさらに、その木に含まれるノード間の最短経路の距離を返します。

さらに、[TR,D,E] = shortestpathtree(___) は、各グラフ エッジが TR 内にあるかどうかを示す logical ベクトル E を返します。

例

指定されたソース ノードからの最短経路

ソース ノードからグラフ内で到達可能な他の各ノードまでの最短経路を求め、結果をプロットします。

有向グラフを作成します。

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

G = 
  digraph with properties:

    Edges: [13x1 table]
    Nodes: [8x0 table]

ノード 1 からグラフ内で到達可能な他の各ノードまでの最短経路を計算します。次に、グラフの上に結果の木をプロットします。

TR = shortestpathtree(G,1);
p = plot(G);
highlight(p,TR,'EdgeColor','r')

ノード 1 からノード 7 までの経路がないので、ノード 7 は木から切断されます。

指定したターゲット ノードまでの最短経路

グラフ内の各ノードからターゲット ノードまでの最短経路を求め、結果をプロットします。

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

s = [1 1 1 1 1 1 1 2 2 7 7 7 7 9 9 3 3 1 6 4 8 10 6 8 4 5];
t = [2 3 4 5 6 8 7 6 7 5 6 8 9 6 8 6 10 10 10 10 10 11 11 11 8 8];
G = graph(s,t);
x = [0 0.5 -0.5 -0.5 0.5 0 1.5 0 2 -1.5 -2];
y = [0 0.5 0.5 -0.5 -0.5 2 0 -2 0 0 0];
plot(G,'XData',x,'YData',y)

グラフ内の各ノードからノード 10 までの最短経路を求めます。結果の木をプロットします。

TR = shortestpathtree(G,'all',10);
plot(TR)

指定されたソース ノードをもつ最短経路のサブセット

単一のソース ノードから複数のターゲット ノードまでの最短経路とその長さを求めます。

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

G = digraph(bucky);
plot(G)

ノード 23 から複数の他のノードまでの最短経路を求めます。OutputForm を cell に指定して、最短経路を cell 配列に返します。2 つの出力を指定して、最短経路の距離も返します。

target = [1 5 13 32 44];
[TR,D] = shortestpathtree(G,23,target,'OutputForm','cell')

TR=5×1 cell array
    {[         23 22 21 4 5 1]}
    {[           23 22 21 4 5]}
    {[23 22 20 16 17 15 14 13]}
    {[      23 22 20 19 18 32]}
    {[      23 24 48 47 46 44]}

D = 1×5

     5     4     7     5     5

tree{j} はノード 23 からノード target(j) までの最短経路であり、その長さは D(j) です。

ノード 21 からノード 5 までの最短経路とその長さを求めます。

path = TR{2}

path = 1×5

    23    22    21     4     5

path_length = D(2)

path_length = 4

入力引数

G — 入力グラフ

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

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

例: G = graph(1,2)

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

s — ソース ノード

ノード インデックス | ノード名 | 'all'

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

• 単独で使用される場合、s は単一のソース ノードを指定しなければなりません。

• t と共に使用する場合、s と t の入力は次を満たさなければなりません。

  • s を単一のソース ノードにして、t に複数のターゲット ノードを指定できます。

  • s に複数のソース ノードを指定して、t に単一のターゲット ノードを指定できます。

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

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

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

例: shortestpathtree(G,'a')

例: shortestpathtree(G,[1 2 3],8)

t — ターゲット ノード

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

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

s および t の入力は次を満たさなければなりません。

• s を単一のソース ノードにして、t に複数のターゲット ノードを指定できます。

• s に複数のソース ノードを指定して、t に単一のターゲット ノードを指定できます。

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

例: shortestpathtree(G,[1 2 3],8)

例: shortestpathtree(G,{'a','b','c'},{'f'})

名前と値の引数

引数のオプションのペアを Name1=Value1,...,NameN=ValueN として指定します。ここで Name は引数名で、Value は対応する値です。名前と値の引数は他の引数の後になければなりませんが、ペアの順序は重要ではありません。

R2021a より前では、コンマを使用してそれぞれの名前と値を区切り、Name を引用符で囲みます。

例: [TR,D] = shortestpathtree(G,s,t,'Method','unweighted','OutputForm','vector')

OutputForm — 出力形式

'tree' (既定値) | 'cell' | 'vector'

出力形式。'OutputForm' と、次の表のいずれかのオプションで構成されるコンマ区切りのペアとして指定します。

オプション	説明
'tree' (既定)	TR は最短経路木を表す有向グラフです。指定すると、3 つ目の出力 E は、各エッジが TR 内にあるかどうかを示す logical ベクトルになります。
'cell'	TR は cell 配列であり、TR{k} は s から t(k) まで、または s(k) から t までの経路を含みます。ノード間に経路がない場合、TR{k} は空です。 s と t がノード名である場合、TR{k} は文字ベクトルの cell 配列です。それ以外の場合、TR{k} は数値ベクトルです。 指定すると、3 つ目の出力 E は、TR の対応する各経路上のエッジを示す cell 配列になります。
'vector'	TR は木を表すベクトルです。 s が単一のソース ノードを含む場合、TR(k) は s から k までの経路上にある、ノード k の先行ノードの ID です。慣例により、TR(s) = 0 です。 s が複数のソース ノードを含む場合、TR(k) は k から t までの経路上にある、ノード k の後続ノードの ID です。慣例により、TR(t) = 0 です。 いずれの場合でも、ノード k が木に含まれないときの TR(k) は NaN です。 指定すると、3 つ目の出力 E は、E(k) がノード k とノード TR(k) を連結する最短経路木のエッジのインデックスを与えるベクトルになります。

例: shortestpathtree(G,s,'OutputForm','vector')

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

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

最短経路アルゴリズム。'Method' と、次の表のいずれかのオプションで構成されるコンマ区切りのペアとして指定します。

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

メモ

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

例: shortestpath(G,s,t,'Method','acyclic')

出力引数

TR — 最短経路木

digraph オブジェクト (既定値) | cell 配列 | ベクトル

最短経路木。'OutputForm' の値に応じて、digraph オブジェクト、cell 配列、またはベクトルとして返されます。グラフのプロットの上に最短経路木を表示するには、関数 highlight を使用します。また、最短経路木のみを表示するには plot(TR) を使用します。

2 つのノード間に複数の最短経路がある場合、TR はそれらの最短経路の 1 つのみを含みます。返される経路は、Method で指定するアルゴリズムによって変化する場合があります。指定されたノードを連結する経路がない場合、TR の出力はエッジ数が 0 のグラフになります。

D — ソース ノードとターゲット ノードの間の距離

ベクトル

ソース ノードとターゲット ノードの間の距離。ベクトルとして返されます。Inf 値は、2 つのノード間に経路がないことを示します。

E — 木または経路上のエッジ

logical ベクトル (既定値) | cell 配列 | ベクトル

木または経路上のエッジ。'OutputForm' の値に応じて、logical ベクトル、cell 配列、またはベクトルとして返されます。

• 'OutputForm' を指定しない場合、つまり 'tree' の値を指定すると、E は、各グラフ エッジが有向グラフ TR 内にあるかどうかを示す logical ベクトルになります。この出力は、highlight の 'Edges' 名前と値のペアと互換し、highlight(p,'Edges',E) などのようになります。

• 'OutputForm' が 'cell' の場合、E は TR 内の対応する経路上のエッジを含む cell 配列になります。

• 'OutputForm' が 'vector' の場合、E は、ノードごとに最短経路木の親ノードにノードを連結するエッジのインデックスを与えるベクトルになります。

ヒント

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

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

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

拡張機能

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

バージョン履歴

R2015b で導入

参考

shortestpath | distances | nearest | graph | digraph