shortestpath

2 つの単一ノード間の最短経路

構文

P = shortestpath(G,s,t)

P = shortestpath(G,s,t,'Method',algorithm)

[P,d] = shortestpath(___)

[P,d,edgepath] = shortestpath(___)

説明

P = shortestpath(G,s,t) は、ソース ノード s から始まりターゲット ノード t で終了する最短経路を計算します。グラフが重み付きの場合 (つまり、G.Edges が変数 Weight を含む)、これらの重みはグラフ エッジの距離として使用されます。それ以外の場合、すべてのエッジの距離は 1 と見なされます。

P = shortestpath(G,s,t,'Method',algorithm) はオプションで最短経路の計算に使用するアルゴリズムを指定します。たとえば、G が重み付きグラフの場合、shortestpath(G,s,t,'Method','unweighted') は G のエッジの重みを無視し、すべてのエッジの重みを 1 として扱います。

[P,d] = shortestpath(___) は前述の構文で示した任意の入力引数を使用して、さらに最短経路の長さ d を返します。

さらに、[P,d,edgepath] = shortestpath(___) は、s から t までの最短経路にあるすべてのエッジのエッジ インデックス edgepath を返します。

例

指定したノード間の最短経路

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

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);
plot(G)

ノード 7 とノード 8 の間の最短経路を計算します。

P = shortestpath(G,7,8)

P = 1×5

     7     1     3     5     8

重み付きグラフの最短経路

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

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

ノード 3 とノード 8 の間の最短経路を求め、2 つの出力を指定して最短経路の長さも返します。

[P,d] = shortestpath(G,3,8)

P = 1×5

     3     9     5     7     8

d = 4

グラフ中央にあるエッジの重みが大きいので、ノード 3 とノード 8 の間の最短経路はエッジの重みが最小であるグラフの境界近くを通過します。この経路の合計長さは 4 です。

エッジの重みを無視した最短経路

カスタム ノード座標を使用し、重み付きエッジをもつグラフを作成してプロットします。

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

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];
p = plot(G,'XData',x,'YData',y,'EdgeLabel',G.Edges.Weight);

グラフ エッジの重みに基づいて、ノード 6 とノード 8 の間の最短経路を求めます。この経路を緑で強調表示します。

[path1,d] = shortestpath(G,6,8)

path1 = 1×5

     6     3     1     4     8

d = 14

highlight(p,path1,'EdgeColor','g')

Method を unweighted に指定してエッジの重みを無視し、すべてのエッジを重み 1 として扱います。この方法では、ノード間に別の経路が得られます。これは、前の方法で最短経路になるには長さが大きすぎた経路です。この経路を赤で強調表示します。

[path2,d] = shortestpath(G,6,8,'Method','unweighted')

path2 = 1×3

     6     9     8

d = 2

highlight(p,path2,'EdgeColor','r')

多重グラフの最短経路

多重グラフの 2 つのノード間の最短経路をプロットし、通過する特定のエッジを強調表示します。

5 つのノードをもつ重み付き多重グラフを作成します。複数のノード ペアの間には複数のエッジがあります。参照用にグラフをプロットします。

G = graph([1 1 1 1 1 2 2 3 3 3 4 4],[2 2 2 2 2 3 4 4 5 5 5 2],[2 4 6 8 10 5 3 1 5 6 8 9]);
p = plot(G,'EdgeLabel',G.Edges.Weight);

ノード 1 とノード 5 の間の最短経路を検出します。複数のノード ペア間に複数のエッジがあるため、shortestpath に 3 つの出力を指定して、最短経路が通過する特定のエッジを返します。

[P,d,edgepath] = shortestpath(G,1,5)

P = 1×5

     1     2     4     3     5

d = 11

edgepath = 1×4

     1     7     9    10

結果は、最短経路の合計の長さが 11 で、G.Edges(edgepath,:) により返されたエッジを通過することを示します。

G.Edges(edgepath,:)

ans=4×2 table
    EndNodes    Weight
    ________    ______

     1    2       2   
     2    4       3   
     3    4       1   
     3    5       5   

関数 highlight を使用し、通過するエッジのインデックスを指定する名前 'Edges' と値のペアを指定して、このエッジ経路を強調表示します。

highlight(p,'Edges',edgepath)

ノード座標からの最短経路

ノード間の距離をエッジの重みとして使用して、グラフ内のノード間の最短経路を求めます。

10 個のノードをもつグラフを作成します。

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

グラフ ノードの x 座標と y 座標を作成します。次に、'XData' および 'YData' の名前と値のペアを指定することで、ノード座標を使用してグラフをプロットします。

x = [1 2 3 2 2.5 4 3 5 3 5];
y = [1 3 4 -1 2 3.5 1 3 0 1.5];
plot(G,'XData',x,'YData',y)

グラフ ノード間のユークリッド距離を計算することにより、グラフにエッジの重みを追加します。この距離は、ノード座標 $\left({\mathit{x}}_{\mathit{i}},{\mathit{y}}_{\mathit{i}}\right)$ から次のように計算されます。

$$\mathit{d}=\sqrt{{\left|\Delta \mathit{x}\right|}^2+{\left|\Delta \mathit{y}\right|}^2}=\sqrt{{\left|{\mathit{x}}_{\mathit{s}}-{\mathit{x}}_{\mathit{t}}\right|}^2+{\left|{\mathit{y}}_{\mathit{s}}-{\mathit{y}}_{\mathit{t}}\right|}^2}.$$

$\Delta \mathit{x}$ と $\Delta \mathit{y}$ を計算するには、まず findedges を使用して、グラフ内の各エッジのソース ノードとターゲット ノードを表すベクトル sn および tn を取得します。次に、sn および tn を使用して x 座標ベクトルと y 座標ベクトルにインデックスを付け、$\Delta \mathit{x}={\mathit{x}}_{\mathit{s}}-{\mathit{x}}_{\mathit{t}}$ と $\Delta \mathit{y}={\mathit{y}}_{\mathit{s}}-{\mathit{y}}_{\mathit{t}}$ を計算します。関数 hypot は二乗和の平方根を計算するため、$\Delta \mathit{x}$ と $\Delta \mathit{y}$ を入力引数として指定して各エッジの長さを計算します。

[sn,tn] = findedge(G);
dx = x(sn) - x(tn);
dy = y(sn) - y(tn);
D = hypot(dx,dy);

距離をエッジの重みとしてグラフに追加して、エッジにラベルが付けられたグラフを再プロットします。

G.Edges.Weight = D';
p = plot(G,'XData',x,'YData',y,'EdgeLabel',G.Edges.Weight);

ノード 1 とノード 10 の間の最短経路を計算し、2 つの出力を指定して経路の長さも返します。重み付きグラフの場合、shortestpath では、エッジの重みを考慮する 'positive' メソッドが自動的に使用されます。

[path,len] = shortestpath(G,1,10)

path = 1×4

     1     4     9    10

len = 6.1503

関数 highlight を使用して、プロット内の経路を表示します。

highlight(p,path,'EdgeColor','r','LineWidth',2)

入力引数

G — 入力グラフ

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

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

例: G = graph(1,2)

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

s,t — ソース ノードとターゲット ノードの ID (個別の引数として指定)

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

ソース ノードとターゲット ノードの ID。ノード インデックスまたはノード名の個別の引数として指定します。

値	例
スカラー ノード インデックス	1
文字ベクトルのノード名	'A'
string スカラーのノード名	"A"

例: shortestpath(G,2,5) は、ノード 2 とノード 5 の間の最短経路を計算します。

例: shortestpath(G,'node1','node2') は、名前付きノード node1 と node2 の間の最短経路を計算します。

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

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

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

オプション	説明
'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')

出力引数

P — ノード間の最短経路

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

ノード間の最短経路。ノード インデックスのベクトルまたはノード名の配列として返されます。ノード間に経路がない場合、P は空 ({}) になります。

• s と t に数値ノード インデックスが含まれる場合、P はノード インデックスの数値ベクトルとなります。

• s と t にノード名が含まれる場合、P はノード名を含む cell 配列または string 配列となります。

s と t の間に複数の最短経路がある場合、P はそれらの最短経路の 1 つのみを含みます。返される経路は、Method に指定するアルゴリズムによって変化する場合があります。

d — 最短経路の距離

スカラー

最短経路の距離。数値スカラーとして返されます。d は、P の連続するノード間にあるエッジの重みの総和です。ノード間に経路がない場合、d は Inf になります。

edgepath — 最短経路上のエッジ

エッジ インデックスのベクトル

最短経路上のエッジ。エッジ インデックスのベクトルとして返されます。多重グラフの場合、この出力には経路上にある 2 つのノード間のエッジが示されます。この出力は、highlight の 'Edges' 名前と値のペアと互換し、highlight(p,'Edges',edgepath) などのようになります。

ヒント

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

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

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

拡張機能

C/C++ コード生成

MATLAB® Coder™ を使用して C および C++ コードを生成します。

使用上の注意事項および制限事項:

• 名前と値の引数は定数でなければなりません。

• 'positive'、'unweighted' および 'auto' のメソッドのみがサポートされています。

• 指定されたノード間に経路がない場合、出力 P および edgepath のサイズは、0 行 0 列ではなく 1 行 0 列になります。

バージョン履歴

R2015b で導入

参考

shortestpathtree | distances | nearest | graph | digraph

×

例を開く

この例の変更されたバージョンがあります。編集された方の例を開きますか?

いいえ、変更されたバージョンを上書きします。 はい