原文传递
考虑交叉口转向的最短路径标号算法
| 专利名称： | 考虑交叉口转向的最短路径标号算法 |
| 摘要： | 本发明公开了一种考虑交叉口转向的最短路径标号算法，涉及对道路最短路径网络表示 方法的改进。该方法先根据路段费用及交叉口转向费用信息生成星型数据结构，通过该数据 结构的层级关系，建立起结点、路段、转向三者之间的对应联系，便于最短路径算法对路网 信息的检索。该算法与传统标号算法步骤基本相同，但在每一步标号时，须对当前结点的下 游结点每一个转向行为分别计算当前结点标号、下游路段费用、下游结点转向费用之和，并 与对应下游结点的最短路径标号做比较，以更新标号，并最终产生最短路径树，在此基础上 求解已知起点和终点之间的最短路径。本发明内存占用空间小，便于网络信息更新，明确了 不同转向动作间的区别。 |
| 专利类型： | 发明专利 |
| 申请人： | 东南大学 |
| 发明人： | 程 琳;杜牧青 |
| 专利状态： | 有效 |
| 申请日期： | 2009-06-11T00:00:00+0800 |
| 发布日期： | 2019-01-01T00:00:00+0800 |
| 申请号： | CN200910033090.3 |
| 公开号： | CN101571995 |
| 代理机构： | 南京经纬专利商标代理有限公司 |
| 代理人： | 许 方 |
| 分类号： | G08G1/00(2006.01)I |
| 申请人地址： | 210096江苏省南京市玄武区四牌楼2号 |
| 主权项： | 1、一种考虑交叉口转向的最短路径标号算法，其特征在于包括如下步骤： 对于有向网络G(V，E)： (1)初始化 创建链表S，将路径起点r加入链表S中，初始化标号如下： |
| 所属类别： | 发明专利 |
检索历史
应用推荐
