最短路径查询方法及查询系统
基本信息
| 申请号 | CN202010578638.9 | 申请日 | - |
| 公开（公告）号 | CN111813883A | 公开（公告）日 | 2020-10-23 |
| 申请公布号 | CN111813883A | 申请公布日 | 2020-10-23 |
| 分类号 | G06F16/29(2019.01)I;G06Q10/04(2012.01)I | 分类 | 计算；推算；计数; |
| 发明人 | 魏斌;朱一;章荐;姜先荣;陈贇;陈瑜 | 申请（专利权）人 | 上海阿尔卡特网络支援系统有限公司 |
| 代理机构 | 上海浦一知识产权代理有限公司 | 代理人 | 上海阿尔卡特网络支援系统有限公司 |
| 地址 | 200120上海市浦东新区福山路380 | ||
| 法律状态 | - | ||
摘要
| 摘要 | 本发明公开了一种最短路径查询方法，包括：通过生成树算法获取最短路径Ri；计算Ri的备用路径集合{RBi}；从备用路径集合{RBi}中获取最短路径R(i+1)；计算最短路径R(i+1)的备用路径集合{RB(i+1)}；利用备用路径集合{RB(i+1)}更新最短路径Ri的备用路径集合{RBi}；从最短路径Ri的备用路径集合{RBi}和最短路径R2的备用路径集合{RB(i+1)}中获取最短路径R(i+2)；循环S4‑S6步骤顺序依次获得不同备用路径集合的最短路径。本发明还公开了一种最短路径查询系统。本发明用于交通网络或通信网络能快速、准确查询topN最短路径，并且本发明能避免最短路径查询效率发生几何级数下降。 |
