کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
481148 | 1446129 | 2010 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the K shortest path trees problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We address the problem of finding the K best path trees connecting a source node with any other non-source node in a directed network with arbitrary lengths. The main result in this paper is the proof that the k th shortest path tree is adjacent to at least one of the previous (k-1)(k-1) shortest path trees. Consequently, we design an O(f(n,m,Cmax)+Km)O(f(n,m,Cmax)+Km) time and O(K+m)O(K+m) space algorithm to determine the K shortest path trees, in a directed network with n nodes, m arcs and maximum absolute length CmaxCmax, where O(f(n,m,Cmax))O(f(n,m,Cmax)) is the best time needed to solve the shortest simple paths connecting a source node with any other non-source node.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 202, Issue 3, 1 May 2010, Pages 628–635
Journal: European Journal of Operational Research - Volume 202, Issue 3, 1 May 2010, Pages 628–635
نویسندگان
Antonio Sedeño-Noda, Carlos González-Martín,