الگوريتم مستطيل آبشاري و ماتريس انتقال در شبكه هاي كوتاه ترين مسير بادور

Cascade rectangle algorithm and transposition matrix in the cycled shortest path networks.

مساله كوتاه ترين مسير يكي از مسائل مشهور، بنيادي و پرطرفدار در نظريه گراف و شبكه است. در ادبيات اين مساله، الگوريتم هاي كاراي زيادي براي تعيين كوتاه ترين مسير و مسافت بين هرزوج گره بر پايه جبر ماتريسي وجود دارد. در اين مقاله، يك الگوريتم دقيق جديد با نام الگوريتم مستطيل آبشاري به كمك ساختار اصلي الگوريتم هاي قبلي و با بهبود روش هاي جديد، ارائه شده است. درالگوريتم ارائه شده سعي مي شود تمام محاسبات و عمليات رياضي الگوريتم در قالب تعدادي مستطيل پياده سازي شود. الگوريتم مستطيل آبشاري، يك الگوريتم كاراست بطوري كه روش اجراي ساده و زمان اجراي سريع دارد. بعلاوه، يك ماتريس جديد براساس ماتريس مسير، با نام ماتريس انتقال تعريف شده كه درتحليل حساسيت و بهينه سازي مجدد شبكه هاي كوتاه ترين مسير كاربرد دارد. درپايان، براي نشان دادن جزئيات اجراي الگوريتم هاي مستطيل آبشاري، فلويد- وارشال، ماتريس تجديد نظرشده هو و ماتريس انتقال، يك مثال بصورت گام به گام حل شده است.

Shortest path problem is among the most interesting problems in the field of graph and network theory. There are many efficient matrix based algorithms for detecting of shortest path and distance between all pairs of this problem in literature. In this paper, a new exact algorithm, named Cascade Rectangle Algorithm, is presented by using main structure of previous exact algorithms and developing some new techniques. In cascade rectangle algorithm, all mathematical calculations and operations execute in multi rectangle structure. This algorithm is an efficient exact algorithm with simple procedure and fast running time. Furthermore, a new matrix on the basis of route matrix, called Transposition Matrix, is defined to apply the sensitivity analysis and reoptimization of the all pairs shortest path networks. Finally, one illustrative example is also solved to show the details of cascade rectangle algorithm, floyd-warshall algorithm, revised matrix algorithm and Transposition Matrix step by step.