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

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

作　　者：胡雄鹰[1,2] 胡斌[1] 张金隆[1] 

机构地区：[1]华中科技大学管理学院,湖北武汉430074 [2]武汉工程大学管理学院,湖北武汉430073

出　　处：《武汉理工大学学报（信息与管理工程版）》2010年第2期197-201,共5页Journal of Wuhan University of Technology：Information & Management Engineering

基　　金：湖北省教育厅科学研究基金资助项目(Q20081502);湖北省企业竞争力研究中心科研基金资助项目(Qyjzl2007y0012)

摘　　要：提出了基于时延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.

关 键 词：随机网络 最短路 随机时延Petri网 

分 类 号：F224.33[经济管理—国民经济]