# Shortest-Path Search Task

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

**Context:**- It can be solved by a Shortest-Path Identification System (that implements a Shortest-Path Search Algorithm).
- It can range from being a Deterministic Shortest-Path Search Task to being a Stochastic Shortest-Path Search Task.

**Example(s):****Counter-Example(s):****See:**Traveling Salesperson.

## 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.

- In graph theory, the

- 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 [math]\displaystyle{ P = (v_1, v_2, \ldots, v_n ) \in V \times V \times \ldots \times V }[/math] such that [math]\displaystyle{ v_i }[/math] is adjacent to [math]\displaystyle{ v_{i+1} }[/math] for [math]\displaystyle{ 1 \leq i \lt n }[/math].

Such a path [math]\displaystyle{ P }[/math] is called a path of length [math]\displaystyle{ n }[/math] from [math]\displaystyle{ v_1 }[/math] to [math]\displaystyle{ v_n }[/math]. (The [math]\displaystyle{ v_i }[/math] 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 [math]\displaystyle{ e_{i, j} }[/math] be the edge incident to both [math]\displaystyle{ v_i }[/math] and [math]\displaystyle{ v_j }[/math].

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

When the graph is unweighted or [math]\displaystyle{ f: E \rightarrow \{c\},\ c \in \mathbb{R}^+ }[/math], 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.

- The
- 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.

- 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.