WOLFRAM

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

GraphPath[g, start, end]

グラフ g の頂点 start と end の間の最短経路を見付ける．

詳細とオプション
Details and Options Details and Options
例題  
例  
オプション  
Method  
特性と関係  
考えられる問題  
インタラクティブな例題  
関連項目
テクニカルノート
関連するガイド
引用書式
GraphUtilities`
GraphUtilities`

GraphPath

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

GraphPath[g, start, end]

グラフ g の頂点 start と end の間の最短経路を見付ける．

詳細とオプション

  • GraphPathの機能はWolfram言語の組込み関数FindShortestPathで利用できるようになった．
  • GraphPathを使うためには，まずグラフユーティリティパッケージをロードしなくてはならない．それにはNeeds["GraphUtilities`"]を実行する必要がある．
  • 以下のオプションを使うことができる：
  • Method Automatic最短経路を見付けるために使用するメソッド
    WeightedTrue距離の計算において辺の重みを使うよう指定する

例題

すべて開く すべて閉じる

例  (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]}&)]

頂点1から頂点3までの最短経路を見付ける：

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

辺の重みを無視して，頂点1から3への最短経路を見付ける：

Wolfram Language code: GraphPath[g, 1, 3, Weighted -> False]

GraphPathの代わりにFindShortestPathが使われるようになった：

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: FindShortestPath[g, 1, 3]
Wolfram Language code: FindShortestPath[g, 1, 3, Method -> "UnitWeight"]

オプション  (1)

Method  (1)

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

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: GraphPath[g, 1, 3, Method -> "Dijkstra"]

ベルマン・フォード(Bellman–Ford)法は使える：

Wolfram Language code: GraphPath[g, 1, 3, Method -> "BellmanFord"]
Wolfram Language code: GraphDistanceMatrix[g, Method -> "Johnson"]

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

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: GraphPath[g, 1, 4, Method -> "Dijkstra"]

ベルマン・フォード法は重みの負閉路を検出する：

Wolfram Language code: GraphPath[g, 1, 4, Method -> "BellmanFord"]

辺の負閉路を持つグラフに対するデフォルトのアルゴリズムは，ベルマン・フォード法である：

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

特性と関係  (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} -> -3.}, {5, 5}];
Wolfram Language code: GraphPlot[g, VertexLabeling -> True, EdgeRenderingFunction -> ({Arrow[#, 0.1], Text[g[[First[#2], Last[#2]]], LineScaledCoordinate[#1], Background -> White]}&)]

頂点1から3までの最短経路を見付ける：

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

辺の重みを考慮に入れて，この経路の距離を見付ける：

Wolfram Language code: GraphDistance[g, 1, 3, Weighted -> True]

辺の重みを無視して，この経路の距離を見付ける：

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

考えられる問題  (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 -> ({Text[g[[First[#2], Last[#2]]], LineScaledCoordinate[#1]], Arrow[#, 0.1]}&)]

辺の重みが負ならば，"Dijkstra"法は使えない：

Wolfram Language code: GraphPath[g, 1, 3, Method -> "Dijkstra"]

"BellmanFord"法を使い，頂点1から3までの最短経路を見付ける：

Wolfram Language code: GraphPath[g, 1, 3, Method -> "BellmanFord"]

インタラクティブな例題  (1)

最短経路を通り頂点1から7まで進む方法：

Wolfram Language code: Needs["GraphUtilities`"]
Wolfram Language code: DynamicModule[{g, coord, path, edges}, g = {1 -> 2, 1 -> 3, 1 -> 17, 2 -> 5, 2 -> 15, 3 -> 4, 3 -> 19, 4 -> 5, 4 -> 20, 5 -> 13, 6 -> 7, 6 -> 8, 6 -> 18, 7 -> 10, 7 -> 11, 8 -> 9, 8 -> 16, 9 -> 10, 9 -> 14, 10 -> 12, 11 -> 13, 11 -> 20, 12 -> 13, 12 -> 15, 14 -> 15, 14 -> 17, 16 -> 17, 16 -> 19, 18 -> 19, 18 -> 20}; coord = GraphCoordinates[g]; path = GraphPath[Flatten[{g, Map[Reverse, g]}], 1, 7]; edges = Transpose[{Drop[path, -1], Drop[path, 1]}]; Manipulate[pe = Take[edges, length]; GraphPlot[g, VertexLabeling -> True, VertexCoordinateRules -> coord, EdgeRenderingFunction -> ({If[MemberQ[pe, #2] || MemberQ[pe, Reverse[#2]], Sequence@@{Thickness[0.01], Red}, Black], Line[#1]}&), ImageSize -> 300], {length, 1, Length[edges], 1}]]
Wolfram Research (2007), GraphPath, Wolfram言語関数， https://reference.wolfram.com/language/GraphUtilities/ref/GraphPath.html.

テキスト

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

CMS

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

APA

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

BibTeX

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

BibLaTeX

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