摘要
求解最短路径问题被广泛用于求解现实中的搜索相关问题。然而现实瞬息万变,一个连通网络的节点常常发生变动,而一旦发生改变,传统算法必须再次计算从源点到各节点的最短路径。然而虽然节点发生了变动,可是最短路径却未必全部发生了改变,这就造成了不必要的浪费。鉴于此提出一种基于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.
出处
《计算机应用与软件》
CSCD
北大核心
2013年第1期171-175,共5页
Computer Applications and Software
