Efficient Associative Algorithm for Finding the Second Simple Shortest Paths in a Digraph

详细信息    查看全文

• 作者：Anna Nepomniaschaya (1) anep@ssd.sscc.ru
• 关键词：Directed weighted graphs &#8211 ; shortest paths tree &#8211 ; second simple shortest paths &#8211 ; associative parallel processor &#8211 ; access data by contents
• 刊名：Lecture Notes in Computer Science
• 出版年：2011
• 出版时间：2011
• 年：2011
• 卷：6873
• 期：1
• 页码：182-191
• 全文大小：159.5 KB
• 参考文献：1. Dijkstra, E.W.: A Note on Two Problems in Connection with Graphs. Numerische Mathematik 1, 269–271 (1959)
  2. Eppstein, D.: Finding the k Shortest Paths. SIAM J. of Computing 28, 652–673 (1998)
  3. Foster, C.C.: Content Addressable Parallel Processors. Van Nostrand Reinhold Company, New York (1976)
  4. Gotthilf, Z., Lewenstein, M.: Improved Algorithms for the k Simple Shortest Paths and the Replacement Paths Problems. Information Processing Letters 109, 352–355 (2009)
  5. Katoh, N., Ibaraki, T., Mine, H.: An Efficient Algorithm for k Shortest Simple Paths. Networks 12, 411–427 (1982)
  6. Lawler, E.L.: A Procedure for Computing the k Best Solutions to Discrete Optimization Problems and its Application to the Shortest Path Problem. Management Science 18, 401–405 (1972)
  7. Nepomniaschaya, A.S.: Language STAR for Associative and Parallel Computation with Vertical Data Processing. In: Mirenkov, N. (ed.) Proc. of the Intern. Conf. ”Parallel Computing Technologies, pp. 258–265. World Scientific, Singapore (1991)
  8. Nepomniaschaya, A.S., Dvoskina, M.A.: A Simple Implementation of Dijkstra’s Shortest Path Algorithm on Associative Parallel Processors. Fundamenta Informaticae 43, 227–243 (2000)
  9. Nepomniaschaya, A.S.: Simultaneous Finding the Shortest Paths and Distances in Directed Graphs Using Associative Parallel Processors. In: Proc. of the Intern. Conf. ”Information Visualization”, IV 2003, pp. 665–670. IEEE Computer Society, Los Alamitos (2003)
  10. Nepomniaschaya, A.S.: Associative Parallel Algorithms for Computing Functions Defined on Paths in Trees. In: Proc. of the Intern. Conf. on Parallel Computing in Electrical Engineering, PARELEC 2002, pp. 399–404. IEEE Computer Society, Los Alamitos (2002)
  11. Roditty, L., Zwick, U.: Replacement paths and k simple shortest paths in unweighted directed graphs. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 249–260. Springer, Heidelberg (2005)
  12. Yen, J.Y.: Finding the k Shortest Loopless Paths in a Network. Management Science 17(11), 712–716 (1971)
• 作者单位：1. Institute of Computational Mathematics and Mathematical Geophysics, Siberian Division of Russian Academy of Sciences, pr. Lavrentieva, 6, Novosibirsk, 630090 Russia
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

We present an associative algorithm for finding the second simple shortest paths from the source vertex to other vertices of a directed weighted graph. Our model of computation (the STAR–machine) simulates the run of associative (content addressable) parallel systems of the SIMD type with vertical processing. We first propose the data structure that uses the graph representation as a list of triples (edge end–points and the weight) and the shortest paths tree obtained by means of the classical Dijkstra algorithm. The associative algorithm is given as the procedure SecondPaths, whose correctness is proved and the time complexity is evaluated.