---
title: "GraphDistanceMatrix"
language: "en"
type: "Symbol"
summary: "As of Version 10, all the functionality of the GraphUtilities package is built into the Wolfram System. >>"
keywords: 
- graph distance graph geodesic all pairs shortest path shortest path shortest distance
canonical_url: "https://reference.wolfram.com/language/GraphUtilities/ref/GraphDistanceMatrix.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: "GraphDistanceMatrix"
    link: "https://reference.wolfram.com/language/ref/GraphDistanceMatrix.en.md"
related_tutorials: 
  - 
    title: "Upgrading from Graph Utilities Package"
    link: "https://reference.wolfram.com/language/Compatibility/tutorial/GraphUtilities.en.md"
---
## GraphUtilities\`

# GraphDistanceMatrix

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

GraphDistanceMatrix[g] gives a matrix in which the (i, j)$$^{\text{th}}$$ entry is the length of a shortest path in g between vertices i and j.

GraphDistanceMatrix[g, Parent] returns a three-dimensional matrix in which the (1, i, j)$$^{\text{th}}$$ entry is the length of a shortest path from i to j and the (2, i, j)$$^{\text{th}}$$ entry is the predecessor of j in a shortest path from i to j.

## Details and Options

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

* To use ``GraphDistanceMatrix``, 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 given:

|          |           |                                                   |
| -------- | --------- | ------------------------------------------------- |
| Method   | Automatic | the method used to compute the shortest path      |
| Weighted | True      | whether edge weights are to be taken into account |

---

## Examples (5)

### Basic Examples (2)

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

This defines a simple 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 calculates the distance between the vertices:

```wl
In[4]:= GraphDistanceMatrix[g]//MatrixForm

Out[4]//MatrixForm=
(⁠|    |    |     |     |    |
| :- | :- | :-- | :-- | :- |
| 0. | 1. | 0.  | -1. | 1. |
| ∞  | 0. | 1.  | ∞   | ∞  |
| ∞  | ∞  | 0.  | ∞   | ∞  |
| ∞  | ∞  | 1.  | 0.  | ∞  |
| ∞  | ∞  | -1. | -2. | 0. |⁠)
```

---

This function has been superseded by ``GraphDistanceMatrix`` in the Wolfram System:

```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]:= GraphDistanceMatrix[g]//MatrixForm

Out[2]//MatrixForm=
(⁠|    |    |     |     |    |
| -- | -- | --- | --- | -- |
| 0. | 1. | 0.  | -1. | 1. |
| ∞  | 0. | 1.  | ∞   | ∞  |
| ∞  | ∞  | 0.  | ∞   | ∞  |
| ∞  | ∞  | 1.  | 0.  | ∞  |
| ∞  | ∞  | -1. | -2. | 0. |⁠)
```

### Scope (1)

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

This defines a simple 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 calculates the distance between the vertices:

```wl
In[4]:= GraphDistanceMatrix[g]//MatrixForm

Out[4]//MatrixForm=
(⁠|    |    |     |     |    |
| :- | :- | :-- | :-- | :- |
| 0. | 1. | 0.  | -1. | 1. |
| ∞  | 0. | 1.  | ∞   | ∞  |
| ∞  | ∞  | 0.  | ∞   | ∞  |
| ∞  | ∞  | 1.  | 0.  | ∞  |
| ∞  | ∞  | -1. | -2. | 0. |⁠)
```

This shows also the predecessors in the shortest path:

```wl
In[5]:=
prd = GraphDistanceMatrix[g, Parent][[2]];
prd//MatrixForm

Out[5]//MatrixForm=
(⁠|   |   |   |   |   |
| :- | :- | :- | :- | :- |
| 1 | 1 | 4 | 5 | 1 |
| 1 | 2 | 2 | 4 | 5 |
| 1 | 2 | 3 | 4 | 5 |
| 1 | 2 | 4 | 4 | 5 |
| 1 | 2 | 4 | 5 | 5 |⁠)
```

The path from 1 to 3 is ``{1, 5, 4, 3}`` :

```wl
In[6]:= Drop[FixedPointList[prd[[1, #]]&, 3], -1]//Reverse

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

This confirms the shortest path:

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

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

### Options (2)

#### Method (2)

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]:= GraphDistanceMatrix[g, Method -> "Dijkstra"]
```

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

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

Both the Floyd–Warshall and Johnson algorithms work:

```wl
In[5]:= GraphDistanceMatrix[g, Method -> "FloydWarshall"]

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

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

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

---

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

This defines a small graph with a negative cycle:

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

In[3]:= 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[3]= [image]
```

The Dijkstra algorithm does not work for negative edge weights:

```wl
In[4]:= GraphDistanceMatrix[g, Method -> "Dijkstra"]
```

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

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

The Floyd–Warshall algorithm does not detect any negative weight cycle, and gives the wrong answer:

```wl
In[5]:= GraphDistanceMatrix[g, Method -> "FloydWarshall"]

Out[5]= {{-1., 3., 3., 1.9999999967268423`*^-7}, {-5., -1., -1., -4.}, {-5., -1., -1., -4.}, {-3., 1., 1., -2.}}
```

The Johnson algorithm detects a negative weight cycle:

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

GraphDistanceMatrix::negc: Negative cycle found. >>

```wl
Out[6]= GraphDistanceMatrix[{{0, 5, 4, 0}, {0, 0, 3, -3}, {0, 1.`*^-7, 0, -1}, {-2, 0, 2, 0}}, Method -> "Johnson"]
```

The default algorithm for graphs with negative edge weights is Johnson:

```wl
In[7]:= GraphDistanceMatrix[g]
```

GraphDistanceMatrix::negc: Negative cycle found. >>

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

## See Also

* [`GraphDistanceMatrix`](https://reference.wolfram.com/language/ref/GraphDistanceMatrix.en.md)
* [GraphPath](https://reference.wolfram.com/language/GraphUtilities/ref/GraphPath.en.md)
* [GraphDistance](https://reference.wolfram.com/language/GraphUtilities/ref/GraphDistance.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)