ABSTRACT
The shortest path problem is a fundamental task in path-planning area and it has been the subject of extensive research resulting in publication of numerous scientific papers. Problem of planning shortest paths, in fact, is one of the most powerful tools for modeling combinatorial optimization problems. The constituents of a general problem for path planning are environment (e.g., a network, a graph, a tree, or a geometric domain); constraints (obstacle avoidance, short length, number of turns depending on the specific application); and a combination of criteria (e.g., optimizing distances or cost functions). Shortest paths in graphs and network (i.e., finding a path connecting two vertices with minimum total length) are well studied, and this classical optimization problem received a lot of attention with significant progress (Ahuja et al., 1993; Pallottino and Scutella, 1998). In the case that all edge weights are nonnegative, the graph had no negative cycles, and the wellknown Dijkstra’s algorithm (Dijkstra, 1959) allowed computing a tree of shortest paths from any source node to all other nodes. This approach is a crucial tool both for
discrete and continuous environment. In fact, although the problems dealt with in this survey have a continuous formulation, these can be reduced to search in a discrete structure due to a finite solution set. Since it is a basic tool modified many times to solve different problems in this context, the Dijkstra’s paradigm is briefly introduced in the next section.
