This is documentation for Mathematica 8, which was
based on an earlier version of the Wolfram Language.
View current documentation (Version 11.2)

GraphDistanceMatrix

GraphDistanceMatrix[g]
gives a matrix in which the ^(th) entry is the length of a shortest path in g between vertices i and j.

returns a three-dimensional matrix in which the ^(th) entry is the length of a shortest path from i to j and the ^(th) entry is the predecessor of j in a shortest path from i to j.
  • The following options can be given:
MethodAutomaticthe method used to compute the shortest path
WeightedTruewhether edge weights are to be taken into account
This defines a simple directed graph:
This calculates the distance between the vertices:
This shows also the predecessors in the shortest path:
The path from 1 to 3 is :
This confirms the shortest path:
Needs["GraphUtilities`"]
This defines a simple directed graph:
In[2]:=
Click for copyable input
In[3]:=
Click for copyable input
Out[3]=
This calculates the distance between the vertices:
In[4]:=
Click for copyable input
Out[4]//MatrixForm=
This shows also the predecessors in the shortest path:
In[5]:=
Click for copyable input
Out[5]//MatrixForm=
The path from 1 to 3 is :
In[6]:=
Click for copyable input
Out[6]=
This confirms the shortest path:
In[7]:=
Click for copyable input
Out[7]=
This defines a small graph:
Because of the negative edge weight, the Dijkstra algorithm cannot be applied:
Both the Floyd-Warshall and Johnson algorithms work:
This defines a small graph with a negative cycle:
The Dijkstra algorithm does not work for negative edge weights:
The Floyd-Warshall algorithm does not detect any negative weight cycle, and gives the wrong answer:
The Johnson algorithm detects a negative weight cycle:
The default algorithm for graphs with negative edge weights is Johnson: