distances
すべてのノード ペアの最短経路の距離
説明
例
すべてのノード ペアの最短経路の距離
グラフを作成してプロットします。
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
入力引数
s
— ソース ノード
'all'
(既定値) | ノード インデックス | ノード名
ソース ノード。1 つ以上のノード インデックスまたはノード名を指定するか、'all'
を指定してすべてのソース ノードを選択します。
次の表に、1 つ以上のノードを数値ノード インデックスまたはノード名のいずれかで参照するさまざまな方法を示します。
形式 | 単一ノード | 複数ノード |
---|---|---|
ノード インデックス | スカラー 例: | ベクトル 例: |
ノード名 | 文字ベクトル 例: | 文字ベクトルの cell 配列 例: |
string スカラー 例: | string 配列 例: |
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' (既定) |
|
'unweighted' | 幅優先検索。すべてのエッジの重みを |
'positive' | ダイクストラ アルゴリズム。すべてのエッジの重みが非負の数でなければなりません。 |
'mixed' (digraph 専用) | 有向グラフのベルマン・フォード アルゴリズム。グラフに負の循環があってはなりません。 同じ問題について |
メモ
多くのグラフについて、'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
MATLAB コマンド
次の MATLAB コマンドに対応するリンクがクリックされました。
コマンドを MATLAB コマンド ウィンドウに入力して実行してください。Web ブラウザーは MATLAB コマンドをサポートしていません。
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)