FindShortestPath

FindShortestPath[g,s,t]

finds the shortest path from source vertex s to target vertex t in the graph g.

FindShortestPath[g,s,All]

generates a ShortestPathFunction[] that can be applied repeatedly to different t.

FindShortestPath[g,All,t]

generates a ShortestPathFunction[] that can be applied repeatedly to different s.

FindShortestPath[g,All,All]

generates a ShortestPathFunction[] that can be applied to different s and t.

FindShortestPath[{vw,},]

uses rules vw to specify the graph g.

Details and Options

Examples

open allclose all

Basic Examples  (1)

Find a shortest path between two individual vertices in a graph:

Highlight the path:

Scope  (9)

Specification  (7)

FindShortestPath works with undirected graphs:

Directed graphs:

Multigraphs:

Mixed graphs:

Weighted graphs:

The shortest path has the smallest total edge weight:

Use rules to specify the graph:

Works with large graphs:

Collection  (2)

Find the shortest paths from one vertex to all vertices:

Apply the ShortestPathFunction to every vertex of the graph:

Find the shortest paths to one vertex from all vertices:

Apply the ShortestPathFunction to every vertex of the graph:

Options  (3)

Method  (3)

The method is automatically chosen depending on input:

"UnitWeight" method will use the weight 1 for every edge:

"Dijkstra" can be used for graphs with positive edge weights only:

Applications  (3)

Find the shortest path in a tree:

Find the shortest path along the seams of a soccer ball:

Create a maze by random depth-first search of a grid graph:

Solve the maze:

Properties & Relations  (1)

The distance between two vertices can be found using the shortest path:

Introduced in 2010
 (8.0)
 |
Updated in 2014
 (10.0)
2015
 (10.3)