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):
  • a Shortest-Cycle Search Task.
  • a Single-Source Shortest Path Task
  • a Single-Destination Shortest Path Task
  • an All-Pairs Shortest Path Task.
  • …
• Counter-Example(s):
  • a Longest Path Identification Task.
• 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.

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

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

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

    When the graph is unweighted or [math]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.
  • 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.

---