WOLFRAM

Wolfram言語 ＆ システムドキュメントセンター

GraphDistanceMatrix[g]

(i, j)番目の要素が，g における頂点 i と j の間の最短経路の長さであるような行列を返す．

GraphDistanceMatrix[g,Parent]

(1,i,j)番目の要素が i から j の最短経路の長さであり，(2,i,j)番目の要素が i から j までの最短経路における j の先行点であるような三次元行列を返す．

詳細とオプション
Details and Options Details and Options
例題  
例  
スコープ  
オプション  
Method  
関連項目
テクニカルノート
関連するガイド
引用書式
GraphUtilities`
GraphUtilities`

GraphDistanceMatrix

バージョン10で，GraphUtilitiesパッケージの機能すべてがWolframシステムに組み込まれた． »

GraphDistanceMatrix[g]

(i, j)番目の要素が，g における頂点 i と j の間の最短経路の長さであるような行列を返す．

GraphDistanceMatrix[g,Parent]

(1,i,j)番目の要素が i から j の最短経路の長さであり，(2,i,j)番目の要素が i から j までの最短経路における j の先行点であるような三次元行列を返す．

詳細とオプション

例題

すべて開く すべて閉じる

例  (2)

Wolfram Language code: Needs["GraphUtilities`"]

簡単な有向グラフを定義する：

Wolfram Language code: g = SparseArray[{{1, 2} -> 1., {2, 3} -> 1., {1, 5} -> 1., {4, 3} -> 1., {5, 4} -> -2.}, {5, 5}];
Wolfram Language code: GraphPlot[g, VertexLabeling -> True, EdgeRenderingFunction -> ({Arrow[#, 0.1], Text[g[[First[#2], Last[#2]]], LineScaledCoordinate[#1], Background -> White]}&)]

頂点間の距離を計算する：

Wolfram Language code: GraphDistanceMatrix[g]//MatrixForm

この関数の代わりにWolframシステムのGraphDistanceMatrixが使われるようになった：

Wolfram Language code: g = WeightedAdjacencyGraph[SparseArray[{{1, 2} -> 1., {2, 3} -> 1., {1, 5} -> 1., {4, 3} -> 1., {5, 4} -> -2.}, {5, 5}, Infinity]]
Wolfram Language code: GraphDistanceMatrix[g]//MatrixForm

スコープ  (1)

Wolfram Language code: Needs["GraphUtilities`"]

簡単な有向グラフを定義する：

Wolfram Language code: g = SparseArray[{{1, 2} -> 1., {2, 3} -> 1., {1, 5} -> 1., {4, 3} -> 1., {5, 4} -> -2.}, {5, 5}];
Wolfram Language code: GraphPlot[g, VertexLabeling -> True, EdgeRenderingFunction -> ({Arrow[#, 0.1], Text[g[[First[#2], Last[#2]]], LineScaledCoordinate[#1], Background -> White]}&)]

頂点間の距離を計算する：

Wolfram Language code: GraphDistanceMatrix[g]//MatrixForm

以下は最短経路の先行点も表す：

Wolfram Language code: prd = GraphDistanceMatrix[g, Parent][[2]]; prd//MatrixForm

1から3までの経路は{1,5,4,3}である：

Wolfram Language code: Drop[FixedPointList[prd[[1, #]]&, 3], -1]//Reverse

最短経路を確認する：

Wolfram Language code: GraphPath[g, 1, 3]

オプション  (2)

Method  (2)

以下で小さいグラフを定義する：

Wolfram Language code: Needs["GraphUtilities`"]
Wolfram Language code: g0 = ToCombinatoricaGraph[{1 -> 2, 2 -> 3, 3 -> 1, 1 -> 3}]; g = SetEdgeWeights[g0, {{1, 2}, {2, 3}, {3, 1}, {1, 3}}, {-1, -2, 3, 1}]; adj = AdjacencyMatrix[g];
Wolfram Language code: GraphPlot[g0, MultiedgeStyle -> True, VertexLabeling -> True, EdgeRenderingFunction -> ({Arrow[#, 0.1], Text[adj[[First[#2], Last[#2]]], LineScaledCoordinate[#1], Background -> White]}&)]

辺の重みが負であるため，ダイクストラ(Dijkstra)法は適用できない：

Wolfram Language code: GraphDistanceMatrix[g, Method -> "Dijkstra"]

ワーシャル・フロイド(Floyd–Warshall)とジョンソン(Johnson)のどちらのアルゴリズムも有効である：

Wolfram Language code: GraphDistanceMatrix[g, Method -> "FloydWarshall"]
Wolfram Language code: GraphDistanceMatrix[g, Method -> "Johnson"]
Wolfram Language code: Needs["GraphUtilities`"]

負閉路を持つ小さいグラフを定義する：

Wolfram Language code: g = {{0, 5, 4, 0}, {0, 0, 3, -3}, {0, 0.0000001, 0, -1}, {-2, 0, 2, 0}};
Wolfram Language code: GraphPlot[{{1 -> 2, 5}, {1 -> 3, 4}, {2 -> 3, 3}, {2 -> 4, -3}, {3 -> 2, 0.0000001}, {3 -> 4, -1}, {4 -> 1, -2}, {4 -> 3, 2}}, VertexLabeling -> True, EdgeRenderingFunction -> ({Arrow[#, .05], Text[#3, LineScaledCoordinate[#1, .3], Background -> White]}&)]

ダイクストラ法は辺の重みが負のときは有効ではない：

Wolfram Language code: GraphDistanceMatrix[g, Method -> "Dijkstra"]

ワーシャル・フロイド法は重みの負閉路を検出しないため，誤った答を出す：

Wolfram Language code: GraphDistanceMatrix[g, Method -> "FloydWarshall"]

ジョンソン法は重みの負閉路を検出する：

Wolfram Language code: GraphDistanceMatrix[g, Method -> "Johnson"]

辺の負閉路を持つグラフに対するデフォルトのアルゴリズムはジョンソン法である：

Wolfram Language code: GraphDistanceMatrix[g]
Wolfram Research (2007), GraphDistanceMatrix, Wolfram言語関数， https://reference.wolfram.com/language/GraphUtilities/ref/GraphDistanceMatrix.html.

テキスト

Wolfram Research (2007), GraphDistanceMatrix, Wolfram言語関数， https://reference.wolfram.com/language/GraphUtilities/ref/GraphDistanceMatrix.html.

CMS

Wolfram Language. 2007. "GraphDistanceMatrix." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/GraphUtilities/ref/GraphDistanceMatrix.html.

APA

Wolfram Language. (2007). GraphDistanceMatrix. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/GraphUtilities/ref/GraphDistanceMatrix.html

BibTeX

@misc{reference.wolfram_2026_graphdistancematrix, author="Wolfram Research", title="{GraphDistanceMatrix}", year="2007", howpublished="\url{https://reference.wolfram.com/language/GraphUtilities/ref/GraphDistanceMatrix.html}", note=[Accessed: 09-August-2026]}

BibLaTeX

@online{reference.wolfram_2026_graphdistancematrix, organization={Wolfram Research}, title={GraphDistanceMatrix}, year={2007}, url={https://reference.wolfram.com/language/GraphUtilities/ref/GraphDistanceMatrix.html}, note=[Accessed: 09-August-2026]}