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

Wolfram Research (2010), FindShortestPath, Wolfram Language function, https://reference.wolfram.com/language/ref/FindShortestPath.html (updated 2015).

#### Text

Wolfram Research (2010), FindShortestPath, Wolfram Language function, https://reference.wolfram.com/language/ref/FindShortestPath.html (updated 2015).

#### CMS

Wolfram Language. 2010. "FindShortestPath." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindShortestPath.html.

#### APA

Wolfram Language. (2010). FindShortestPath. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindShortestPath.html

#### BibTeX

@misc{reference.wolfram_2024_findshortestpath, author="Wolfram Research", title="{FindShortestPath}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindShortestPath.html}", note=[Accessed: 13-June-2024 ]}

#### BibLaTeX

@online{reference.wolfram_2024_findshortestpath, organization={Wolfram Research}, title={FindShortestPath}, year={2015}, url={https://reference.wolfram.com/language/ref/FindShortestPath.html}, note=[Accessed: 13-June-2024 ]}