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.