ドキュメンテーション

最新のリリースでは、このページがまだ翻訳されていません。 このページの最新版は英語でご覧になれます。

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')

Methodunweighted を指定してエッジの重みを無視し、すべてのエッジを重み 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)

入力引数

すべて折りたたむ

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

例: G = graph(1,2)

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

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

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

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

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

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

オプション説明
'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 は空 ({}) になります。

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

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

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

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

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

ヒント

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

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

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

R2015b で導入