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:

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: 21-November-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: 21-November-2024 ]}