TOPICS

# Shortest Path Problem

The shortest path problem seeks to find the shortest path (a.k.a. graph geodesic) connecting two specific vertices of a directed or undirected graph. The length of the graph geodesic between these points is called the graph distance between and . Common algorithms for solving the shortest path problem include the Bellman-Ford algorithm and Dijkstra's algorithm.

The Wolfram Language function FindShortestPath[g, u, v] can be used to find one (of possibly mutiple) shortest path between vertices and in a graph .

The so-called reaching algorithm can solve the shortest path problem on an -edge graph in steps for an acyclic digraph although it allows edges to be traversed opposite their direction and given a negative length.

All-Pairs Shortest Path, Bellman-Ford Algorithm, Dijkstra's Algorithm, Floyd-Warshall Algorithm, Graph Distance, Graph Geodesic, Longest Path, Reaching Algorithm

Portions of this entry contributed by Andreas Lauschke

## Explore with Wolfram|Alpha

More things to try:

## References

Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, 2003.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 224-227, 1990.

## Referenced on Wolfram|Alpha

Shortest Path Problem

## Cite this as:

Lauschke, Andreas and Weisstein, Eric W. "Shortest Path Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ShortestPathProblem.html