Main Content

shortestpath

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

説明

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)

Figure contains an axes object. The axes object contains an object of type graphplot.

ノード 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)

Figure contains an axes object. The axes object contains an object of type graphplot.

ノード 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);

Figure contains an axes object. The axes object contains an object of type graphplot.

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

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

     6     3     1     4     8

d = 14
highlight(p,path1,'EdgeColor','g')

Figure contains an axes object. The axes object contains an object of type graphplot.

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

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

     6     9     8

d = 2
highlight(p,path2,'EdgeColor','r')

Figure contains an axes object. The axes object contains an object of type graphplot.

多重グラフの 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);

Figure contains an axes object. The axes object contains an object of type graphplot.

ノード 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)

Figure contains an axes object. The axes object contains an object of type graphplot.

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

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)

Figure contains an axes object. The axes object contains an object of type graphplot.

グラフ ノード間のユークリッド距離を計算することにより、グラフにエッジの重みを追加します。この距離は、ノード座標 (xi,yi) から次のように計算されます。

d=|Δx|2+|Δy|2=|xs-xt|2+|ys-yt|2.

ΔxΔy を計算するには、まず findedges を使用して、グラフ内の各エッジのソース ノードとターゲット ノードを表すベクトル sn および tn を取得します。次に、sn および tn を使用して x 座標ベクトルと y 座標ベクトルにインデックスを付け、Δx=xs-xtΔy=ys-yt を計算します。関数 hypot は二乗和の平方根を計算するため、ΔxΔ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);

Figure contains an axes object. The axes object contains an object of type graphplot.

ノード 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)

Figure contains an axes object. The axes object contains an object of type graphplot.

入力引数

すべて折りたたむ

入力グラフ。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 つあると、負の循環が作成されます。

拡張機能

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

バージョン履歴

R2015b で導入