Journal of Operational Research and Its Applications
تحقیق در عملیات در کاربردهای آن
jor
Basic Sciences
http://jamlu.liau.ac.ir
1
admin
2251-7286
2251-9807
8
10.61186/jamlu
14
8888
13
fa
jalali
1396
9
1
gregorian
2017
12
1
14
4
online
1
fulltext
fa
الگوریتم مستطیل آبشاری و ماتریس انتقال در شبکه های کوتاه ترین مسیر بادور
Cascade rectangle algorithm and transposition matrix in the cycled shortest path networks.
تخصصي
Special
پژوهشي
Research
<p dir="RTL">مساله کوتاه ترین مسیر یکی از مسائل مشهور، بنیادی و پرطرفدار در نظریه گراف و شبکه است. در ادبیات این مساله، الگوریتم های کارای زیادی برای تعیین کوتاه ترین مسیر و مسافت بین هرزوج گره بر پایه جبر ماتریسی وجود دارد. در این مقاله، یک الگوریتم دقیق جدید با نام الگوریتم مستطیل آبشاری به کمک ساختار اصلی الگوریتم های قبلی و با بهبود روش های جدید، ارائه شده است. درالگوریتم ارائه شده سعی می شود تمام محاسبات و عملیات ریاضی الگوریتم در قالب تعدادی مستطیل پیاده سازی شود<span dir="LTR">.</span> الگوریتم مستطیل آبشاری، یک الگوریتم کاراست بطوری که روش اجرای ساده و زمان اجرای سریع دارد. بعلاوه، یک ماتریس جدید براساس ماتریس مسیر، با نام ماتریس انتقال تعریف شده که درتحلیل حساسیت و بهینه سازی مجدد شبکه های کوتاه ترین مسیر کاربرد دارد. درپایان، برای نشان دادن جزئیات اجرای الگوریتم های مستطیل آبشاری، فلوید- وارشال، ماتریس تجدید نظرشده هو و ماتریس انتقال، یک مثال بصورت گام به گام حل شده است<span dir="LTR">.</span></p>
<p>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.</p>
الگوریتم های شبکه کوتاه ترین مسیر با دور, الگوریتم آبشاری, روش ماتریس تجدید نظر شده, الگوریتم فلوید و وارشال, روش آبشاری تجدید نظر شده
Cycled shortest path networks algorithms, Cascade algorithm, Revised matrix method, Floyd-Warshall algorithm, Revised cascade method
67
87
http://jamlu.liau.ac.ir/browse.php?a_code=A-11-1125-1&slc_lang=fa&sid=1
Asghar
Aini
اصغر
عینی
ainiasghar@gmail.com
10031947532846005054
10031947532846005054
Yes
Sharif University of Technology
دانشگاه صنعتی شریف
Kourosh
Eshghi
کورش
عشقی
Eshghi@sharif.edu
10031947532846005055
10031947532846005055
No
Sharif University of Technology
دانشگاه صنعتی شریف