# 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 that can be applied repeatedly to different t.

FindShortestPath[g,All,t]

generates a that can be applied repeatedly to different s.

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

FindShortestPath[{vw,},]

uses rules vw to specify the graph g.

# Details and Options • FindShortestPath[g,s,t] gives a path from s to t.
• FindShortestPath[g,s] is equivalent to FindShortestPath[g,s,All].
• is equivalent to .
• For an unweighted graph, edge length is assumed to be 1.
• For a weighted graph, edge length is taken to be the weight.
• A Method option can also be given. Possible Method settings include:
•  "BellmanFord" supports positive and negative weights "Dijkstra" supports positive weights
• FindShortestPath works with undirected graphs, directed graphs, weighted graphs, multigraphs, and mixed graphs.

# 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)