maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2013-2-5-22mais-202Research ArticleОригинальные статьиArticlesАссоциативный параллельный алгоритм для динамической обработки дерева кратчайших путейAssociative Parallel Algorithm for Dynamic Update of the Shortest Paths TreeНепомнящаяАнна ШмилевнаNepomniaschayaA. S.

канд. физ.-мат. наук, старший научный сотрудник,

630090, Россия, г. Новосибирск, проспект Академика Лаврентьева, 6

канд. физ.-мат. наук, старший научный сотрудник,

prospect Akademika Lavrentjeva, 6, Novosibirsk, 630090, Russia

anep@ssd.sscc.ruИнститут вычислительной математики и математической геофизики СО РАНРоссияInstitute of Computational Mathematics and Mathematical Geophysics SB RASRussian Federation201320042013202522Copyright © Непомнящая А.Ш., 20132013Непомнящая А.Ш.Nepomniaschaya A.S.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/202

В работе строится эффективный ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей после удаления одной дуги из ориентированного взвешенного графа. С этой целью вначале описывается используемая структура данных и ее построение, а также приводится STAR–машина, которая моделирует работу ассоциативных (контекстно–адресуемых) параллельных систем с простыми процессорными элементами и вертикальной обработкой информации. На этой модели ассоциативный параллельный алгоритм представляется в виде главной процедуры DeleteArcSPT, использующей группу вспомогательных процедур для выполнения его отдельных частей. Доказана корректность процедуры DeleteArcSPT и показано, что на STAR-машине она выполняется за время O(hk), где h – число битов, которое требуется для кодирования длины максимального кратчайшего пути, а k – число вершин, для которых вычисляются новые кратчайшие пути после удаления одной дуги из исходного графа.

The paper proposes an efficient associative algorithm for dynamic update of the shortest paths tree of a directed weighted graph after deleting an edge. To this end, we provide the data structure and its building along with the STAR–machine that simulates the run of associative (content–addressable) parallel systems with simple single–bit processing elements and vertical processing. The associative algorithm is represented on the STAR–machine as the main procedure DeleteArcSPT that uses some auxiliary procedures. By means of the auxiliary procedures, we execute some parts of the associative parallel algorithm for dynamic update of the shortest paths tree after deleting an arc from the graph. We prove correctness of the procedure DeleteArcSPT and all its parts. We obtain that on the STAR–machine this procedure takes O(hk) time, where h is the number of bits required for coding the maximum of the shortest paths weights and k is the number of vertices, whose shortest paths change after deleting an edge from the given graph.  

ориентированный взвешенный графдерево кратчайших путейматрица смежностидекрементальный алгоритмассоциативный параллельный процессорdirected weighted graph$the shortest paths treeadjacency matrixdecremental algorithmassociative parallel processorReferencesRamalingam G. Bounded Incremental Computation // Lecture Notes in Computer Science. Berlin: Springer–Verlag, 1996. Vol. 1089. P. 30–51.Ramalingam G. Bounded Incremental Computation // Lecture Notes in Computer Science. Berlin: Springer–Verlag, 1996. Vol. 1089. P. 30–51.Ramalingam G., Reps T. An incremental algorithm for a generalization of the shortest paths problem // Journal of Algorithms. Academic Press. 1996. Vol. 21. P. 267–305.Ramalingam G., Reps T. An incremental algorithm for a generalization of the shortest paths problem // Journal of Algorithms. Academic Press. 1996. Vol. 21. P. 267–305.Frigioni D., Marchetti-Spaccamela A., Nanni U. Semi–dynamic algorithms for maintaining single source shortest paths trees // Algorithmica. Berlin: Springer–Verlag, 1998. Vol. 25. P. 250–274.Frigioni D., Marchetti-Spaccamela A., Nanni U. Semi–dynamic algorithms for maintaining single source shortest paths trees // Algorithmica. Berlin: Springer–Verlag, 1998. Vol. 25. P. 250–274.Frigioni D., Marchetti-Spaccamela A., Nanni U. Fully dynamic algorithms for maintaining shortest paths trees // Journal of Algorithms. Academic Press. 2000. Vol. 34. P. 351–381.Frigioni D., Marchetti-Spaccamela A., Nanni U. Fully dynamic algorithms for maintaining shortest paths trees // Journal of Algorithms. Academic Press. 2000. Vol. 34. P. 351–381.Frigioni D., Marchetti-Spaccamela A., Nanni U. Fully dynamic shortest paths in digraphs with arbitrary arc weights // Journal of Algorithms. Elsevier Science. 2003. Vol. 49. P. 86–113.Frigioni D., Marchetti-Spaccamela A., Nanni U. Fully dynamic shortest paths in digraphs with arbitrary arc weights // Journal of Algorithms. Elsevier Science. 2003. Vol. 49. P. 86–113.Nepomniaschaya A. S. Associative version of the Ramalingam decremental algorithm for dynamic updating the single-sink shortest paths subgraph // Proc. of the 10-th International Conference on Parallel Computing Technologies, PaCT-2009, Novosibirsk, Russia. Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2009. Vol. 5698. P. 257–268.Nepomniaschaya A. S. Associative version of the Ramalingam decremental algorithm for dynamic updating the single-sink shortest paths subgraph // Proc. of the 10-th International Conference on Parallel Computing Technologies, PaCT-2009, Novosibirsk, Russia. Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2009. Vol. 5698. P. 257–268.Nepomniaschaya A. S. Language STAR for associative and parallel computation with vertical data processing // Proc. of the International Conference “Parallel Computing Technologies”. World Scientific, Singapore, 1991. P. 258–265.Nepomniaschaya A. S. Language STAR for associative and parallel computation with vertical data processing // Proc. of the International Conference “Parallel Computing Technologies”. World Scientific, Singapore, 1991. P. 258–265.Dijkstra E.W. A note on two problems in connection with graphs // Numerische Mathematik. 1959. Vol. 1. P. 269–271.Dijkstra E.W. A note on two problems in connection with graphs // Numerische Mathematik. 1959. Vol. 1. P. 269–271.Foster C.C. Content Addressable Parallel Processors. New York: Van Nostrand Reinhold Company, 1976.Foster C.C. Content Addressable Parallel Processors. New York: Van Nostrand Reinhold Company, 1976.Непомнящая А.Ш., Владыко М. А. Сравнение моделей ассоциативных параллельных вычислениний // Программирование. 1997. № 6. С. 41–50 (English transl.: Nepomniaschaya A.Sh., Vladyko M.A. A Comparison of Associative Computation Models //Programming and Computer Software. 1997. V. 23, № 6. P. 319–324).Непомнящая А.Ш., Владыко М. А. Сравнение моделей ассоциативных параллельных вычислениний // Программирование. 1997. № 6. С. 41–50 (English transl.: Nepomniaschaya A.Sh., Vladyko M.A. A Comparison of Associative Computation Models //Programming and Computer Software. 1997. V. 23, № 6. P. 319–324).Nepomniaschaya A. S. Solution of path problems using associative parallel processors // Proc. of the Intern. Conf. on Parallel and Distributed Systems, ICPADS’97. Korea, Seoul, IEEE Computer Society Press, 1997. P. 610–617.Nepomniaschaya A. S. Solution of path problems using associative parallel processors // Proc. of the Intern. Conf. on Parallel and Distributed Systems, ICPADS’97. Korea, Seoul, IEEE Computer Society Press, 1997. P. 610–617.Nepomniaschaya A. S., Dvoskina M. A. A simple implementation of Dijkstra’s shortest path algorithm on associative parallel processors // Fundamenta Informaticae. IOS Press, 2000. Vol. 43. P. 227-243.Nepomniaschaya A. S., Dvoskina M. A. A simple implementation of Dijkstra’s shortest path algorithm on associative parallel processors // Fundamenta Informaticae. IOS Press, 2000. Vol. 43. P. 227-243.Nepomniaschaya A. S. Simultaneous finding the shortest paths and distances in directed graphs using associative parallel processors // Proc. of the Intern. Conf. “Information Visualization (IV 2003). England, London, IEEE Computer Society, Los Alamitos, 2003. P. 665–670.Nepomniaschaya A. S. Simultaneous finding the shortest paths and distances in directed graphs using associative parallel processors // Proc. of the Intern. Conf. “Information Visualization (IV 2003). England, London, IEEE Computer Society, Los Alamitos, 2003. P. 665–670.

The authors declare that there are no conflicts of interest present.