网络最短路径的一种更新策略

• 作者: 程远
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: Dijkstra算法 最短路径 连通网络
• 年，卷（期）: 2013,（1）
• 所属期刊栏目: 应用技术与研究
• 页码范围: 171-175
• 页数: 5页
• 分类号: TP3-05
• 字数: 7093字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386x.2013.01.041

摘要

求解最短路径问题被广泛用于求解现实中的搜索相关问题.然而现实瞬息万变,一个连通网络的节点常常发生变动,而一旦发生改变,传统算法必须再次计算从源点到各节点的最短路径.然而虽然节点发生了变动,可是最短路径却未必全部发生了改变,这就造成了不必要的浪费.鉴于此提出一种基于Dijkstra算法的最短路更新策略,将Dijkstra算法做了改进,使其不必重新计算也能在连通图发生改变的时候更新最短路径.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	程远	中国科学技术大学计算机科学与技术学院	4	17	2.0	4.0