---
title: "GraphPath"
language: "en"
type: "Symbol"
summary: "As of Version 10, all the functionality of the GraphUtilities package is built into the Wolfram System. >>"
keywords: 
- graph path shortest path shortest distance graph geodesic
canonical_url: "https://reference.wolfram.com/language/GraphUtilities/ref/GraphPath.html"
source: "Wolfram Language Documentation"
related_guides: 
  - 
    title: "Graphs & Networks"
    link: "https://reference.wolfram.com/language/guide/GraphsAndNetworks.en.md"
  - 
    title: "Graph Visualization"
    link: "https://reference.wolfram.com/language/guide/GraphVisualization.en.md"
  - 
    title: "Computation on Graphs"
    link: "https://reference.wolfram.com/language/guide/ComputationOnGraphs.en.md"
  - 
    title: "Graph Construction & Representation"
    link: "https://reference.wolfram.com/language/guide/GraphConstructionAndRepresentation.en.md"
  - 
    title: "Graphs and Matrices"
    link: "https://reference.wolfram.com/language/guide/GraphsAndMatrices.en.md"
  - 
    title: "Graph Properties & Measurements"
    link: "https://reference.wolfram.com/language/guide/GraphPropertiesAndMeasurements.en.md"
  - 
    title: "Graph Operations and Modifications"
    link: "https://reference.wolfram.com/language/guide/GraphModifications.en.md"
  - 
    title: "Statistical Analysis"
    link: "https://reference.wolfram.com/language/guide/RandomGraphs.en.md"
  - 
    title: "Social Network Analysis"
    link: "https://reference.wolfram.com/language/guide/SocialNetworks.en.md"
  - 
    title: "Graph Properties"
    link: "https://reference.wolfram.com/language/guide/GraphProperties.en.md"
  - 
    title: "Mathematical Data Formats"
    link: "https://reference.wolfram.com/language/guide/MathematicalDataFormats.en.md"
  - 
    title: "Discrete Mathematics"
    link: "https://reference.wolfram.com/language/guide/DiscreteMathematics.en.md"
related_functions: 
  - 
    title: "FindShortestPath"
    link: "https://reference.wolfram.com/language/ref/FindShortestPath.en.md"
related_tutorials: 
  - 
    title: "Upgrading from Graph Utilities Package"
    link: "https://reference.wolfram.com/language/Compatibility/tutorial/GraphUtilities.en.md"
---
## GraphUtilities\`

# GraphPath

⚠ As of Version 10, all the functionality of the ``GraphUtilities`` package is built into the Wolfram System. [`>>`](https://reference.wolfram.com/language/ref/FindShortestPath.en.md)

GraphPath[g, start, end] finds a shortest path between vertices start and end in graph g.

## Details and Options

* ``GraphPath`` functionality is now available in the built-in Wolfram Language function ``FindShortestPath``.

* To use ``GraphPath``, you first need to load the [Graph Utilities Package](https://reference.wolfram.com/language/GraphUtilities/guide/GraphUtilitiesPackage.en.md) using ``Needs["GraphUtilities`"]``.

* The following options can be used:

|          |           |                                                                   |
| -------- | --------- | ----------------------------------------------------------------- |
| Method   | Automatic | method to use to find the shortest path                           |
| Weighted | True      | specify whether edge weight is to be used in calculating distance |

---

## Examples (6)

### Basic Examples (2)

```wl
In[1]:= Needs["GraphUtilities`"]
```

This defines a small directed graph:

```wl
In[2]:= g = SparseArray[{{1, 2} -> 1., {2, 3} -> 1., {1, 5} -> 1., {4, 3} -> 1., {5, 4} -> -2.}, {5, 5}];

In[3]:= GraphPlot[g, VertexLabeling -> True, EdgeRenderingFunction -> ({Arrow[#, 0.1], Text[g[[First[#2], Last[#2]]], LineScaledCoordinate[#1], Background -> White]}&)]

Out[3]= [image]
```

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

```wl
In[4]:= GraphPath[g, 1, 3]

Out[4]= {1, 5, 4, 3}
```

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

```wl
In[5]:= GraphPath[g, 1, 3, Weighted -> False]

Out[5]= {1, 2, 3}
```

---

``GraphPath`` has been superseded by ``FindShortestPath`` :

```wl
In[1]:= g = WeightedAdjacencyGraph[SparseArray[{{1, 2} -> 1., {2, 3} -> 1., {1, 5} -> 1., {4, 3} -> 1., {5, 4} -> -2.}, {5, 5}, Infinity]]

Out[1]= [image]

In[2]:= FindShortestPath[g, 1, 3]

Out[2]= {1, 5, 4, 3}

In[3]:= FindShortestPath[g, 1, 3, Method -> "UnitWeight"]

Out[3]= {1, 2, 3}
```

### Options (1)

#### Method (1)

This defines a small graph:

```wl
In[1]:= Needs["GraphUtilities`"]

In[2]:=
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];

In[3]:= GraphPlot[g0, MultiedgeStyle -> True, VertexLabeling -> True, EdgeRenderingFunction -> ({Arrow[#, 0.1], Text[adj[[First[#2], Last[#2]]], LineScaledCoordinate[#1], Background -> White]}&)]

Out[3]= [image]
```

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

```wl
In[4]:= GraphPath[g, 1, 3, Method -> "Dijkstra"]
```

GraphPath::negw: Method->Dijkstra can not be applied to a graph containing negative edge weight. >>

```wl
Out[4]= GraphPath["⁃Graph:<"4", "3", ""Directed"">⁃", 1, 3, Method -> "Dijkstra"]
```

The Bellman–Ford algorithm works:

```wl
In[5]:= GraphPath[g, 1, 3, Method -> "BellmanFord"]

Out[5]= {1, 2, 3}

In[6]:= GraphDistanceMatrix[g, Method -> "Johnson"]

Out[6]= {{0., -1., -3.}, {1., 0., -2.}, {3., 2., 0.}}
```

This defines a small graph with a negative cycle:

```wl
In[7]:= g = {{0, 5, 4, 0}, {0, 0, 3, -3}, {0, 0.0000001, 0, -1}, {-2, 0, 2, 0}};

In[8]:= 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]}&)]

Out[8]= [image]
```

The Dijkstra algorithm does not work for negative edge weights:

```wl
In[9]:= GraphPath[g, 1, 4, Method -> "Dijkstra"]
```

GraphPath::negw: Method->Dijkstra can not be applied to a graph containing negative edge weight. >>

```wl
Out[9]= GraphPath[{{0, 5, 4, 0}, {0, 0, 3, -3}, {0, 1.`*^-7, 0, -1}, {-2, 0, 2, 0}}, 1, 4, Method -> "Dijkstra"]
```

The Bellman–Ford algorithm detects a negative weight cycle:

```wl
In[10]:= GraphPath[g, 1, 4, Method -> "BellmanFord"]
```

GraphPath::negc: Negative cycle found. >>

```wl
Out[10]= GraphPath[{{0, 5, 4, 0}, {0, 0, 3, -3}, {0, 1.`*^-7, 0, -1}, {-2, 0, 2, 0}}, 1, 4, Method -> "BellmanFord"]
```

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

```wl
In[11]:= GraphPath[g, 1, 4]
```

GraphPath::negc: Negative cycle found. >>

```wl
Out[11]= GraphPath[{{0, 5, 4, 0}, {0, 0, 3, -3}, {0, 1.`*^-7, 0, -1}, {-2, 0, 2, 0}}, 1, 4]
```

### Properties & Relations (1)

This defines a small directed graph:

```wl
In[1]:= Needs["GraphUtilities`"]

In[2]:= g = SparseArray[{{1, 2} -> 1., {2, 3} -> 1., {1, 5} -> 1., {4, 3} -> 1., {5, 4} -> -3.}, {5, 5}];

In[3]:= GraphPlot[g, VertexLabeling -> True, EdgeRenderingFunction -> ({Arrow[#, 0.1], Text[g[[First[#2], Last[#2]]], LineScaledCoordinate[#1], Background -> White]}&)]

Out[3]= [image]
```

This finds the shortest path from vertex 1 to 3:

```wl
In[4]:= GraphPath[g, 1, 3]

Out[4]= {1, 5, 4, 3}
```

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

```wl
In[5]:= GraphDistance[g, 1, 3, Weighted -> True]

Out[5]= -1.
```

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

```wl
In[6]:= GraphDistance[g, 1, 3]

Out[6]= 2
```

### Possible Issues (1)

```wl
In[1]:= Needs["GraphUtilities`"]
```

This defines a small directed graph:

```wl
In[2]:= g = SparseArray[{{1, 2} -> 1., {2, 3} -> 1., {1, 5} -> 1., {4, 3} -> 1., {5, 4} -> -2.}, {5, 5}];

In[3]:= GraphPlot[g, VertexLabeling -> True, EdgeRenderingFunction -> ({Text[g[[First[#2], Last[#2]]], LineScaledCoordinate[#1]], Arrow[#, 0.1]}&)]

Out[3]= [image]
```

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

```wl
In[4]:= GraphPath[g, 1, 3, Method -> "Dijkstra"]
```

GraphPath::negw: Method->Dijkstra can not be applied to a graph containing negative edge weight. >>

```wl
Out[4]= GraphPath[SparseArray["<"5">", {5, 5}], 1, 3, Method -> "Dijkstra"]
```

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

```wl
In[5]:= GraphPath[g, 1, 3, Method -> "BellmanFord"]

Out[5]= {1, 5, 4, 3}
```

### Interactive Examples (1)

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

```wl
In[1]:= Needs["GraphUtilities`"]

In[2]:=
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}]]

Out[2]= DynamicModule[«3»]
```

## See Also

* [`FindShortestPath`](https://reference.wolfram.com/language/ref/FindShortestPath.en.md)
* [GraphDistance](https://reference.wolfram.com/language/GraphUtilities/ref/GraphDistance.en.md)
* [GraphDistanceMatrix](https://reference.wolfram.com/language/GraphUtilities/ref/GraphDistanceMatrix.en.md)

## Tech Notes

* [Upgrading from Graph Utilities Package](https://reference.wolfram.com/language/Compatibility/tutorial/GraphUtilities.en.md)
* [Graph Utilities Package](https://reference.wolfram.com/language/GraphUtilities/tutorial/GraphUtilities.en.md)

## Related Guides

* [Graph Utilities Package](https://reference.wolfram.com/language/GraphUtilities/guide/GraphUtilitiesPackage.en.md)
* [Graphs & Networks](https://reference.wolfram.com/language/guide/GraphsAndNetworks.en.md)
* [Graph Visualization](https://reference.wolfram.com/language/guide/GraphVisualization.en.md)
* [Computation on Graphs](https://reference.wolfram.com/language/guide/ComputationOnGraphs.en.md)
* [Graph Construction & Representation](https://reference.wolfram.com/language/guide/GraphConstructionAndRepresentation.en.md)
* [Graphs and Matrices](https://reference.wolfram.com/language/guide/GraphsAndMatrices.en.md)
* [Graph Properties & Measurements](https://reference.wolfram.com/language/guide/GraphPropertiesAndMeasurements.en.md)
* [Graph Operations and Modifications](https://reference.wolfram.com/language/guide/GraphModifications.en.md)
* [Statistical Analysis](https://reference.wolfram.com/language/guide/RandomGraphs.en.md)
* [Social Network Analysis](https://reference.wolfram.com/language/guide/SocialNetworks.en.md)
* [Graph Properties](https://reference.wolfram.com/language/guide/GraphProperties.en.md)
* [Mathematical Data Formats](https://reference.wolfram.com/language/guide/MathematicalDataFormats.en.md)
* [Discrete Mathematics](https://reference.wolfram.com/language/guide/DiscreteMathematics.en.md)