GraphDistanceMatrix
GraphDistanceMatrix[g]
gives a matrix in which the (i,j) 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) entry is the length of a shortest path from i to j and the (2,i,j) 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 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
open allclose allBasic Examples (2)
This defines a simple directed graph:
This calculates the distance between the vertices:
This function has been superseded by GraphDistanceMatrix in the Wolfram System:
Scope (1)
Options (2)
Method (2)
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:
Text
Wolfram Research (2007), GraphDistanceMatrix, Wolfram Language function, https://reference.wolfram.com/language/GraphUtilities/ref/GraphDistanceMatrix.html.
CMS
Wolfram Language. 2007. "GraphDistanceMatrix." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/GraphUtilities/ref/GraphDistanceMatrix.html.
APA
Wolfram Language. (2007). GraphDistanceMatrix. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/GraphUtilities/ref/GraphDistanceMatrix.html