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.

	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]=

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: