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

GraphPath


finds a shortest path between vertices start and end in graph g.
  • The following options can be used:
MethodAutomaticmethod to use to find the shortest path
WeightedTruespecifies 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:
In[2]:=
Click for copyable input
In[3]:=
Click for copyable input
Out[3]=
This finds the shortest path from vertex 1 to vertex 3:
In[4]:=
Click for copyable input
Out[4]=
This finds the shortest path from vertex 1 to vertex 3, ignoring the edge weights:
In[5]:=
Click for copyable input
Out[5]=
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: