WOLFRAM

Wolfram 语言与系统参考资料中心

GraphPath[g,start,end]

finds a shortest path between vertices start and end in graph g.

更多信息和选项
Details and Options Details and Options
范例  
基本范例  
Options  
Method  
Properties & Relations  
Possible Issues  
Interactive Examples  
参见
技术笔记
相关指南
按以下格式引用：
GraphUtilities`
GraphUtilities`

GraphPath

As of Version 10, all the functionality of the GraphUtilities package is built into the Wolfram System. »

GraphPath[g,start,end]

finds a shortest path between vertices start and end in graph g.

更多信息和选项

范例

打开所有单元 关闭所有单元

基本范例  (2)

Wolfram Language code: Needs["GraphUtilities`"]

This defines a small directed graph:

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

This finds the shortest path from vertex 1 to vertex 3:

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

This finds the shortest path from vertex 1 to vertex 3, ignoring the edge weights:

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

GraphPath has been superseded by 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"]

Options  (1)

Method  (1)

This defines a small graph:

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

Because of the negative edge weight, the Dijkstra algorithm cannot be applied:

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

The Bellman–Ford algorithm works:

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

This defines a small graph with a negative cycle:

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

The Dijkstra algorithm does not work for negative edge weights:

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

The Bellman–Ford algorithm detects a negative weight cycle:

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

The default algorithm for graphs with negative edge weights is Bellman–Ford:

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

Properties & Relations  (1)

This defines a small directed graph:

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

This finds the shortest path from vertex 1 to 3:

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

This finds the distance of this path, taking into account the edge weights:

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

This finds the distance of this path, ignoring the edge weights:

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

Possible Issues  (1)

Wolfram Language code: Needs["GraphUtilities`"]

This defines a small directed graph:

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

If there are negative edge weights, the "Dijkstra" method cannot be used:

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

This finds the shortest path from vertex 1 to vertex 3 using the "BellmanFord" method:

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

Interactive Examples  (1)

This shows how to travel from vertex 1 to 7 through the shortest path:

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 语言. 2007. "GraphPath." Wolfram 语言与系统参考资料中心. Wolfram Research. https://reference.wolfram.com/language/GraphUtilities/ref/GraphPath.html.

APA

Wolfram 语言. (2007). GraphPath. Wolfram 语言与系统参考资料中心. 追溯自 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: 19-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: 19-August-2026]}