(Redirected from Shortest Path Problem)

A Shortest-Path Search Task is a optimal-path search task that requires shortest paths (in a graph).

References

2013

• http://en.wikipedia.org/wiki/Shortest_path_problem
• In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

This is analogous to the problem of finding the shortest path between two intersections on a road map: the graph's vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of its road segment.

• http://en.wikipedia.org/wiki/Shortest_path_problem#Definition
• The shortest path problem can be defined for graphs whether undirected, directed, or mixed. It is defined here for undirected graphs; for directed graphs the definition of path requires that consecutive vertices be connected by an appropriate directed edge.

Two vertices are adjacent when they are both incident to a common edge.

A path in an undirected graph is a sequence of vertices $P = (v_1, v_2, \ldots, v_n ) \in V \times V \times \ldots \times V$ such that $v_i$ is adjacent to $v_{i+1}$ for $1 \leq i \lt n$.

Such a path $P$ is called a path of length $n$ from $v_1$ to $v_n$. (The $v_i$ are variables; their numbering here relates to their position in the sequence and needs not to relate to any canonical labeling of the vertices.)

Let $e_{i, j}$ be the edge incident to both $v_i$ and $v_j$.

Given a real-valued weight function $f: E \rightarrow \mathbb{R}$, and an undirected (simple) graph $G$, the shortest path from $v$ to $v'$ is the path $P = (v_1, v_2, \ldots, v_n )$ (where $v_1 = v$ and $v_n = v'$) that over all possible $n$ minimizes the sum $\sum_{i =1}^{n-1} f(e_{i, i+1}).$

When the graph is unweighted or $f: E \rightarrow \{c\},\ c \in \mathbb{R}^+$, this is equivalent to finding the path with fewest edges.

The problem is also sometimes called the single-pair shortest path problem, to distinguish it from the following variations:

• The single-source shortest path problem, in which we have to find shortest paths from a source vertex v to all other vertices in the graph.
• The single-destination shortest path problem, in which we have to find shortest paths from all vertices in the directed graph to a single destination vertex v. This can be reduced to the single-source shortest path problem by reversing the arcs in the directed graph.
• The all-pairs shortest path problem, in which we have to find shortest paths between every pair of vertices v, v' in the graph.
• These generalizations have significantly more efficient algorithms than the simplistic approach of running a single-pair shortest path algorithm on all relevant pairs of vertices.