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

AN UPDATE STRATEGY FOR SHORTEST PATH OF GRAPH NET

作　　者：程远[1,2] 

机构地区：[1]中国科学技术大学计算机科学与技术学院,安徽铜陵244000 [2]铜陵学院,安徽铜陵244000

出　　处：《计算机应用与软件》2013年第1期171-175,共5页Computer Applications and Software

摘　　要：求解最短路径问题被广泛用于求解现实中的搜索相关问题。然而现实瞬息万变,一个连通网络的节点常常发生变动,而一旦发生改变,传统算法必须再次计算从源点到各节点的最短路径。然而虽然节点发生了变动,可是最短路径却未必全部发生了改变,这就造成了不必要的浪费。鉴于此提出一种基于Dijkstra算法的最短路更新策略,将Dijkstra算法做了改进,使其不必重新计算也能在连通图发生改变的时候更新最短路径。Solving the shortest path has been widely applied to solve searching relative issues in reality. However, as the reality is ever- changing, the node which connects the graph net is frequently changing as well, and, once it＇ s changed, the traditional algorithm has to recalculate the shortest path from the source point to each node. But, though the node has changed, it does not mean that all of the shortest path will be changed too, which will result in unnecessary waste. In this regard, in the article we propose a Dijkatra algorithm-based shortest path update policy, make the improvement on Dijkatra algorithm, and enable it to update the shortest path without recalculation when the connected graph changes.

关 键 词：DIJKSTRA算法 最短路径 连通网络 

分 类 号：TP3-05[自动化与计算机技术—计算机科学与技术]