پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 44 |
| تعداد شمارهها | 1,877 |
| تعداد مقالات | 15,278 |
| تعداد مشاهده مقاله | 43,731,783 |
| تعداد دریافت فایل اصل مقاله | 17,564,052 |
A new $O(m+k n \log \overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs | ||
| Transactions on Combinatorics | ||
| مقاله 55، دوره 5، شماره 3، آذر 2016، صفحه 23-31 اصل مقاله (233.57 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2016.12602 | ||
| نویسنده | ||
| Mehdi Kadivar* | ||
| Academic member of Shahrekord University | ||
| چکیده | ||
| We give an algorithm, called T$^{*}$, for finding the k shortest simple paths connecting a certain pair of nodes, $s$ and $t$, in a acyclic digraph. First the nodes of the graph are labeled according to the topological ordering. Then for node $i$ an ordered list of simple $s-i$ paths is created. The length of the list is at most $k$ and it is created by using tournament trees. We prove the correctness of T$^{*}$ and show that its worst-case complexity is $O(m+k n \log \overline{d})$ in which n is the number of nodes and m is the number of arcs and $\overline{d}$ is the mean degree of the graph. The algorithm has a space complexity of $O(kn)$ which entails an important improvement in space complexity. An experimental evaluation of T$^{*}$ is presented which confirms the advantage of our algorithm compared to the most efficient $k$ shortest paths algorithms known so far. | ||
| کلیدواژهها | ||
| $k$ shortest path problem؛ complexity of algorithms؛ ranking of paths | ||
| مراجع | ||
|
1] H. Aljazzar and S. Leue, $K^{*}$: a heuristic search algorithm for finding the k shortest paths, Artificial Intelligence, 175 no. 18 (2011) 2129–2154. [2] J. A. Azevedo, M. E. O. Santos Costa, J. J. E. R. Silvestre Madeira and E. Q. V. Martins, An algorithm for the ranking of shortest paths, European J. Oper. Res., 69 (1993) 97–106. [3] C. Caliskan, A computational study of the capacity scaling algorithm for the maximum flow problem, Comput. Oper. Res., 39 no. 11 (2012) 2742–2747. [4] Y. L. Chen, Finding thekquickest simple paths in a network, Information Processing Letters, 50 (1994) 89–92. [5] D. Eppstein, Finding the $K$ shortest paths, SIAM J. Comput., 28 (1999) 652–673. [6] G. Feng, Finding $K$ Shortest Simple Paths in Directed Graphs: A Node Classification Algorithm, Networks, 64 (2014) 6–17. [7] G. N. Frederickson, An optimal algorithm for selection in a min-heap, Inform. and Comput., 104 (1993) 197–214. [8] G. N. Frederickson, Ambivalent data structures for dynamic 2-edge-connectivity and $k$ smallest spanning trees, in: 32nd Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. Press, Los Alamitos, CA, 1991 632–641. [9] B. L. Fox, k-th shortest paths and applications to the probabilistic networks, ORSA/TIMS Joint National Mtg., 23 (1975) p. B263. [10] Z. Gotthilf and M. Lewenstein, Improved algorithms for the $k$ simple shortest paths and the replacement paths problems, Inform. Process. Lett., 109 (2009) 352–355. [11] W. Hoffman and R. Pavley, A method for the solution of the $N$ th best path problem, J. Assoc. Comput. Mach., 6 (1959) 506–514. [12] V. M. Jimenez and A. Marzal, A lazy version of Eppstein’s shortest paths algorithm, in: 2nd International Workshop on Experimental and Efficient Algorithms, in: Lecture Notes in Computer Science, Springe, 2003 179–190. [13] N. Katoh, T. Ibaraki and H. Mine, An efficient algorithm for $k$ shortest simple paths, Networks, 12 (1982) 411–427. [14] S. P. Miaou and S. M. Chin, Computing $K$-shortest path for nuclear spent fuel highway transportation, Eur. J. Operational Research, 53 (1991) 64–80. [15] J. W. Suurballe, Disjoint paths in a network, Networks, 4 (1974) 125–145. [16] J. Y. Yen, Finding the $K$ shortest loopless paths in a network, Management Sci., 17 (1971) 712–716. | ||
|
آمار تعداد مشاهده مقاله: 3,546 تعداد دریافت فایل اصل مقاله: 3,542 |
||