شماره راهنما :
1673 دكتري
پديد آورنده :
سپهري فر، محمدكاظم
عنوان :
تسريع در يافتن كوتاهترين مسيرها از يك گره با كاهش وزن مسيرهاي منتهي به گره‌هاي مقصد
گرايش تحصيلي :
مهندسي كامپيوتر
محل تحصيل :
اصفهان : دانشگاه صنعتي اصفهان
صفحه شمار :
پانزده، 92ص.: مصور، جدول، نمودار
استاد راهنما :
علي فانيان
استاد مشاور :
محمدسعيد صباغ
توصيفگر ها :
مسئله‌ي كوتاهترين مسير , گراف جهت‌دار و وزن‌دار نامنفي , شبكه با چندين گره‌ي مقصد , الگوريتم دايكسترا , بهبود متوسط مرتبه زماني
تاريخ ورود اطلاعات :
1399/10/12
رشته تحصيلي :
مهندسي كامپيوتر
دانشكده :
مهندسي برق و كامپيوتر
تاريخ ويرايش اطلاعات :
1399/10/30
چكيده انگليسي :
94 Faster shortest path computation from a single node by reducing the weight of paths to the destination nodes Mohammad Kazem Sepehrifar mk sepehrifar@ec iut ac ir October 1 2020 Department of Electrical and Computer EngineeringIsfahan University of Technology 84156 83111 Isfahan IranDr Ali Fanian a fanian@cc iut ac irDr Mohammad Saeid Sabbagh Department Graduate Program Coordinator Department of Electrical and Computer Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Department of Industrial Engineering Isfahan University of Technology Isfahan 84156 83111 IranAbstractThe shortest path problem is the problem of finding a path with minimum total weight from a source node toeach destination node in a network The existing solution to this fundamental problem searches the shortestpaths to all network nodes until it meets the given multiple destination nodes By granting preference to routesof each destination node the proposed algorithm meets the destination nodes faster Compared to the existingsolution the average time improvement of the proposed algorithm is in order where is the number ofnodes in the given network The experimental analysis results on real world datasets and simulated randomnetworks show the superiority of the proposed algorithm to the existing solution This remarkable improvementmakes the proposed algorithm applicable in all related applications Key WordsShortest path problem Single source node Multiple destination nodes Directed non negative weighted graph Dijkstra s algorithm Average case time complexityIntroductionThe shortest path problem is a fundamental problem in computer science On a givennetwork graph the solution to this problem searches for a path with the minimumsummation of edge weights among all accessible routes from a source node to a set ofdestination nodes The recent existing algorithm to solve the multiple destination shortestpath problem is multi destination Dijkstra s algorithm MDDA MDDA searches theshortest paths to all network nodes until it meets the desired destination nodes The recentimprovements developed to solve this problem are suitable for specific applications and donot address any solution to this problem in general The running time of the existing solution MDDA significantly increases when the number of vertices is increased This algorithmtends to expand the search space uniformly in all directions which searches all paths withthe same priority Finding a more efficient solution to this problem is still a challenge MethodsOur motivation is to develop a faster algorithm for finding the shortest paths in a non negative weighted directed network when the multiple destination nodes are given Theproposed algorithm multi destination oriented algorithm MDOA emphasizes thesearching extent and improves the algorithm performance To achieve this goal the new ideais based on considering the effect of edge weights of the input graph on searching speed Utilizing the idea MDOA differentiates the shortest path from the other paths and gives the
استاد راهنما :
علي فانيان
استاد مشاور :
محمدسعيد صباغ
