摘要
在无向图上,对于任意源点—目的点点对,给出了一个新的k最短路算法.这一算法按长度递增给出k最短路路径.算法的复杂度为O(m+nlgn+mlgk).这一算法基于动态规划,首先计算出每一点到源点的最短距离,然后从目的点回溯到源点.根据各点的最短距离信息,给出一棵以目的点为根节点,源点为叶子的树表示的k最短路路径.
A new algorithm is described to enumerate the k shortest paths connecting a given pair of vertices in a undirected graph. Our algorithm outputs the paths in order by length in total time O（ m ＋ nlogn ＋ mlogk）. The algorithm is bases on dynamic programming. Firstly compute the shortest distances for every vertex to the source, later trace to the source from the destination on the ground of the distance data and list the k shortest paths.
出处
《山东大学学报（理学版）》
CAS
CSCD
北大核心
2006年第4期40-43,共4页
Journal of Shandong University(Natural Science)
关键词
动态规划
最短路径
无向图
dynamic programming
shortest path
undirected graph
