Shortest path problem
[1] The problem of finding the shortest path between two intersections on a road map may be modeled as a special case of the shortest path problem in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the length or distance of each segment.
The shortest path problem can be defined for graphs whether undirected, directed, or mixed.
The problem is also sometimes called the single-pair shortest path problem, to distinguish it from the following variations: 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.
An algorithm using topological sorting can solve the single-source shortest path problem in time Θ(E + V) in arbitrarily-weighted directed acyclic graphs.
A network flow problem typically involves a directed graph where each edge represents a pipe, wire, or road, and each edge has a capacity, which is the maximum amount that can flow through it.
The all-pairs shortest paths problem for unweighted directed graphs was introduced by Shimbel (1953), who observed that it could be solved by a linear number of matrix multiplications that takes a total time of O(V4).
Shortest path algorithms are applied to automatically find directions between physical locations, such as driving directions on web mapping websites like MapQuest or Google Maps.
[10] If one represents a nondeterministic abstract machine as a graph where vertices describe states and edges describe possible transitions, shortest path algorithms can be used to find an optimal sequence of choices to reach a certain goal state, or to establish lower bounds on the time needed to reach a given state.
For example, if vertices represent the states of a puzzle like a Rubik's Cube and each directed edge corresponds to a single move or turn, shortest path algorithms can be used to find a solution that uses the minimum possible number of moves.
A more lighthearted application is the games of "six degrees of separation" that try to find the shortest path in graphs like movie stars appearing in the same film.
Other applications, often studied in operations research, include plant and facility layout, robotics, transportation, and VLSI design.
Such graphs are special in the sense that some edges are more important than others for long-distance travel (e.g. highways).
[13] There are a great number of algorithms that exploit this property and are therefore able to compute the shortest path a lot quicker than would be possible on general graphs.
In the first phase, the graph is preprocessed without knowing the source or target node.
The algorithm with the fastest known query time is called hub labeling and is able to compute shortest path on the road networks of Europe or the US in a fraction of a microsecond.
The TSP is the problem of finding the shortest path that goes through every vertex exactly once, and returns to the start.
Different computers have different transmission speeds, so every edge in the network has a numeric weight equal to the number of milliseconds it takes to transmit a message.
Our goal is to send a message between two points in the network in the shortest time possible.
If we know the transmission-time of each computer (the weight of each edge), then we can use a standard shortest-paths algorithm.
A possible solution to this problem is to use a variant of the VCG mechanism, which gives the computers an incentive to reveal their true weights.
In some cases, the main goal is not to find the shortest path, but only to detect if the graph contains a negative cycle.
[21][22][23] Most of the classic shortest-path algorithms (and new ones) can be formulated as solving linear systems over such algebraic structures.
[24] More recently, an even more general framework for solving these (and much less obviously related problems) has been developed under the banner of valuation algebras.
[26][27] There is no accepted definition of optimal path under uncertainty (that is, in stochastic road networks).
One common definition is a path with the minimum expected travel time.
The main advantage of this approach is that it can make use of efficient shortest path algorithms for deterministic networks.
However, the resulting optimal path may not be reliable, because this approach fails to address travel time variability.
So, they find the probability distribution of total travel duration using different optimization methods such as dynamic programming and Dijkstra's algorithm .
[29] The terms travel time reliability and travel time variability are used as opposites in the transportation research literature: the higher the variability, the lower the reliability of predictions.
To account for variability, researchers have suggested two alternative definitions for an optimal path under uncertainty.
