TOPICS
Search

Shortest Path Problem


The shortest path problem seeks to find the shortest path (a.k.a. graph geodesic) connecting two specific vertices (u,v) of a directed or undirected graph. The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v. 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 u and v in a graph g.

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


See also

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

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

Subject classifications