The shortest path problem is concerned with finding the shortest path from a specified origin to a specified destination in a given network while minimizing the total cost associated with the path.


--------------------------------------------------------------------------------------------------
The applications of the shortest path problem include vehicle routing in transportation systems [1], traffic routing in communication networks [2], [3], and path planning in robotic systems [4]-[6].



[4] S. Jun and K. G. Shin, 
�gShortest path planning in distributed workspace using dominance relation,�h
 IEEE Trans. Robot. Automat., vol. 7, pp.
342.350, 1991.

[5] P. L. Lin and S. Chang, 
�gA shortest path algorithm for a nonrotating object among obstacles of arbitrary shapes,�h
 IEEE Trans. Syst., Man,
Cybern., vol. 23, pp. 825.833, 1993. => done

[6] P. Soueres and J.-P. Laumond, 
�gShortest paths synthesis for a car-like robot,�h
 IEEE Trans. Automat. Contr., vol. 41, pp. 672.688, 1996. => done


Shortest-path-planning-in-distributed-workspace-using-dominance-relation
A-shortest-path-algorithm-for-a-nonrotating-object-among-obstacles-of-arbitrary-shapes
Shortest-paths-synthesis-for-a-car-like-robot


--------------------------------------------------------------------------------------------------
The shortest path problem has been investigated extensively. The well-known algorithms for solving the shortest path problem include the O(n2) Bellman�fs dynamic programming algorithm for directed acycle networks, the O(n2) Dijkstra-like labeling algorithm and the O(n3) Bellman.Ford successive approximation algorithm for networks with nonnegative cost coefficients only, where n denotes the number of vertices in the network. See [7] for a comprehensive coverage of these algorithms.

     [7] E. L. Lawler, Combinatorial Optimization: Networks and Matroids.
New York: Holt, Rinehart, and Winston, 1976, pp. 59.108.=> almost done but alas


Combinatorial-Optimization Networks-and-Matroids