GRAPH UTILITIES PACKAGE SYMBOL

GraphPath

finds a shortest path between vertices start and end in graph g.

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

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: