公开(公告)号：CN106503789A

公开(公告)日：2017-03-15

申请号：CN201610980706.8

申请日：2016-11-08

Applicant: 西安电子科技大学宁波信息技术研究院

Inventor： 裴婉婉 ,  吴炜

IPC: G06N3/00 ,  G01C21/20 ,  G05B13/04

CPC classification number: G06N3/006 ,  G01C21/20 ,  G05B13/041

Abstract: 本发明公开了一种基于迪杰斯特拉和最大最小蚁群的无环最短路径搜索方法，主要解决现有技术时间复杂度高、路径权值不够优的问题。其实现步骤为：1)构造满足路径关系的有权有向图G，使用剪枝剔除不需要的节点和有向边得到剪枝后的有权有向图G1；2)将剪枝后的有权有向图G1简化为只包含源节点、必经节点集、目的节点的简单图G2；3)在简单图G2中使用结合迪杰斯特拉算法的最大最小蚁群方法寻找最优路径并输出。本发明与现有技术相比，具有求解速度快、最短路径优的特点，可用于网络路由系统中路径选择、交通运输中线路规划场景。