基于STPN求解随机网络最短路的仿真方法

Simulation Approach to Find the Shortest Path of Stochastic Network Based on STPN

提出了基于时延Petri网求解网络最短路的仿真方法,该方法保持了Dijkstra算法的特性,充分利用了Petri网的并发特性,可迅速而自动地求出最短路,所需计算量仅正比于最短路的长度,与路径图的复杂程度及路径图中的通路总数无关。并将该算法推广到随机网络情形,提出基于随机时延Petri网(STPN)的随机网络最短路仿真算法,可迅速而准确地找到起点与终点之间的随机网络最短路的分布函数。

The simulation method was presented for solving the shortest path of network based on timed Petri net.The method maintained the characteristics of the Dijkstra algorithm,and made full use of the concurrent characteristics of Petri nets.The shortest path can be calculated quickly and automatically.The required computation quantity was only proportional to the length of the shortest path,and it was unrelated to the complexity or the total number of pathway of the road map.The algorithm was extended to the case of stochastic network while a simulation algorithm of the shortest path of stochastic network was provided based on stochastic timed Petri net（STPN）,which can quickly and accurately find the distribution function of the shortest path of stochastic network between the starting point and the end.