基于加权标识S-图的最短路径研究  

Study of Shortest Path Based on Weighted Identification S-graph

作　　者：李书举[1] 李文敬[1] 王汝凉[1] 马俊[1] 刘阿宁[1] 

机构地区：[1]广西师范学院计算机与信息工程学院,南宁530001

出　　处：《计算机工程》2011年第15期46-48,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60864001);广西自然科学基金资助项目(0991105);广西教育厅科研基金资助项目(200911MS144)

摘　　要：为解决智能交通系统中交通运输网络分析和最短路径问题,提出加权标识S-图最短路径算法。根据Petri网基本原理和加权S-图的特点,给出交通网络加权S-图的网模型。阐述加权标识S-图最短路径的基本原理、求解加权标识S-图的最短路径定理及证明。通过交通运输网络示例和实验对算法进行验证,对比分析算法性能。结果表明,加权标识S-图最短路径算法能够更有效地求解交通网络最短路径。In order to solve the intelligent transportation system in transportation network analysis and the shortest path problem, this paper proposes a weighted identification S-graph shortest path algorithm. According to the basic principle and Petri nets weighted S-graph characteristics, it puts forward the weighted S-graph network model. A weighted identification shortest path S-graph basic principle is illustrated, a weighted S-map identifies the shortest path. Through the transportation network of sample and experiment verified, the algorithm is compared and analyzed. Experimental results show that the weighted identification S-graph shortest path algorithm for solving the transport network is an effective method for the shortest path.

关 键 词：PETRI网 加权标识 S-图 网模型 最短路径 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]