کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4629898 | 1340588 | 2012 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An efficient time and space K point-to-point shortest simple paths algorithm
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات کاربردی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We address the problem identifying the K best point-to-point simple paths connecting a given pair of nodes in a directed network with arbitrary lengths. The main result in this paper is the proof that a path tree containing the kth point-to-point shortest simple path can be obtained by using one of the previous (k â 1) path trees containing each one of the previous (k â 1) best point-to-point shortest simple paths. The proof implies that at most n single-source shortest path computations (re-optimizations) in a network with non-negative length arcs are made in each iteration of the method. In the “optimistic” case, this strategy only needs O(m) time to compute the best “neighbor” associated with a path tree, that is, the second shortest simple path given a shortest simple path. The algorithm runs in O(K nf(n, m, Cmax)) time and uses O(K + m) space to determine the K point-to-point shortest simple paths in a directed network with n nodes, m arcs and maximum absolute length Cmax. Here, O(f(n, m, Cmax)) is the best time needed to determine the shortest simple paths connecting a source node with any other non-source node in a network with non-negative length arcs. We improve required space in Yen's algorithm by a multiplicative factor of O(n2) for each best solution. Moreover, our algorithm runs in the “optimistic” case in O(Kf (n, m, Cmax)) time. This affirmation is confirmed by an experimental study where O(K) shortest paths are used to determine the K point-to-point shortest simple paths in two versions of our algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics and Computation - Volume 218, Issue 20, 15 June 2012, Pages 10244-10257
Journal: Applied Mathematics and Computation - Volume 218, Issue 20, 15 June 2012, Pages 10244-10257
نویسندگان
Antonio Sedeño-Noda,