The Shortest Path Algorithm Based on Petri Net
The Dijkstra algorithm is the classic algorithm to solve the shortest path problem, but the solving process is relatively complicated. As the visual graphics ability and good computer skills of Petri Net, it is used to solve the shortest path problem, and
- PDF / 330,708 Bytes
- 9 Pages / 439.36 x 666.15 pts Page_size
- 37 Downloads / 263 Views
The Shortest Path Algorithm Based on Petri Net Yu-jie Zheng, Kai-hu Hou, Wei-zhen Liao, and Lin Yang
Abstract The Dijkstra algorithm is the classic algorithm to solve the shortest path problem, but the solving process is relatively complicated. As the visual graphics ability and good computer skills of Petri Net, it is used to solve the shortest path problem, and according to the thought of directed Petri Net and transition enabled rules, Petri Net algorithm of solving the shortest path problem is designed. Compared to the Dijkstra algorithm, this algorithm which omits the P, T tabs and œ, S functions of the Dijkstra algorithm, can make the solution of the shortest path simpler and more convenient, improve the solution efficiency, and at the same time provide convenience for achieving algorithm objectively using computer. Keywords Dijkstra algorithm • Petri Net algorithm • Petri Net of directed network • The shortest path problem
21.1 Introduction The shortest path problem is one of the most important optimization problems. It can be directly applied to solve many of the problems in the actual production, such as pipe laying, circuit arrangement, factory layout, equipment updating, and it is often as one of the basic tools, used to solve the problems of the optimization of the others (Sun Zhixin et al. 2007). Theoretically, the question has many algorithms, the classic Dijkstra algorithm is put forward in 1959, namely Dijkstra method. This algorithm is a kind of excellent shortest path algorithm, which has a wide range of applications in the network calculation and optimization (Noshita 1985). But there are heavy steps and complicated calculation, its availability is not Y. Zheng () • K. Hou • W. Liao • L. Yang Department of Industrial Engineering, Kunming University of Science and Technology, Kunming, People’s Republic of China e-mail: [email protected]; kaihu [email protected] E. Qi et al. (eds.), The 19th International Conference on Industrial Engineering and Engineering Management, DOI 10.1007/978-3-642-37270-4 21, © Springer-Verlag Berlin Heidelberg 2013
221
222
Y. Zheng et al.
satisfactory. In recent years, some scholars have put forward many new methods to solve this problem. In the first literature, an adjacency list storage model with heuristic information was proposed, the process of initial population with heuristic information and chromosome coding, and the strategy of dynamic adjustment of the fitness function were presented (Li Xiongfei et al. 2011). In the second literature, a path nodes-driven idea was introduced, which derived from the destination doesdrive idea. Using the idea, an algorithm called least-cost shortest path tree (LCAPT) was designed (Zhou Ling and Wang Jianxin 2011). In the third literature, Dijkstra algorithm was revised, and all shortest paths can be given according to the number of edges by applying Yen algorithm (Wang Zhijian et al. 2010). In the fourth literature, the solving random network of the shortest circuit simulation method based on STPN was proposed, the s
Data Loading...
