This is documentation for Mathematica 8, which was
based on an earlier version of the Wolfram Language.
 GRAPH UTILITIES PACKAGE SYMBOL

# GraphDistanceMatrix

 GraphDistanceMatrix[g] gives a matrix in which the entry is the length of a shortest path in g between vertices i and j. returns a three-dimensional matrix in which the entry is the length of a shortest path from i to j and the entry is the predecessor of j in a shortest path from i to j.
• 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
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:
 Out[3]=
This calculates the distance between the vertices:
 Out[4]//MatrixForm=
This shows also the predecessors in the shortest path:
 Out[5]//MatrixForm=
The path from 1 to 3 is :
 Out[6]=
This confirms the shortest path:
 Out[7]=
 Options   (2)
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: