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

# GraphPath

 finds a shortest path between vertices start and end in graph g.
• The following options can be used:
 Method Automatic method to use to find the shortest path Weighted True specifies whether edge weight is to be used in calculating distance
This defines a small directed graph:
This finds the shortest path from vertex 1 to vertex 3:
This finds the shortest path from vertex 1 to vertex 3, ignoring the edge weights:
Needs["GraphUtilities`"]
This defines a small directed graph:
 Out[3]=
This finds the shortest path from vertex 1 to vertex 3:
 Out[4]=
This finds the shortest path from vertex 1 to vertex 3, ignoring the edge weights:
 Out[5]=
 Options   (1)
This defines a small graph:
Because of the negative edge weight, the Dijkstra algorithm cannot be applied:
The Bellman-Ford algorithm works:
This defines a small graph with a negative cycle:
The Dijkstra algorithm does not work for negative edge weights:
The Bellman-Ford algorithm detects a negative weight cycle:
The default algorithm for graphs with negative edge weights is Bellman-Ford:
This defines a small directed graph:
This finds the shortest path from vertex 1 to 3:
This finds the distance of this path, taking into account the edge weights:
This finds the distance of this path, ignoring the edge weights:
This defines a small directed graph:
If there are negative edge weights, the method cannot be used:
This finds the shortest path from vertex 1 to vertex 3 using the method:
This shows how to travel from vertex 1 to 7 through the shortest path: