Graph-based Shortest Path Optimization D ijkstra Algorithm Improvement

سال انتشار: 1401
محل انتشار: هفتمین کنفرانس بین المللی مهندسی برق ،الکترونیک و شبکه های هوشمند
کد COI اختصاصی: EESCONF07_034
زبان مقاله: انگلیسی
تعداد مشاهده: 175

نویسندگان

Alzahra University

Sharif University of Technology

چکیده

In this paper we introduce the draft of a new graph-based algorithm for optimizationof shortest path problem. Our algorithm is based on the Dijkstra and A* algorithm,which is usually used for path planning. It was tested on the shortest path planningProblem against Dijkstra classic implementation. The comparison of these resultsshowed that the proposed algorithm exhibited a promising convergence rate toward anoptimal solution. The time is the total length or time that we estimate for the shortestpath in a graph. In most of the tested cases, our proposed algorithm managed to find asolution faster than the A* algorithm; in five cases, the graph-based algorithm found asolution at the same time as the A* algorithm. Our results also showed that the mannerof priority calculation had a non-negligible impact on solutions, and that anappropriately chosen priority calculation could improve them.

کلیدواژه ها

dynamic programming, Dijkstra algorithm, A* algorithm, graph-basedalgorithm, shortest path planning, optimization.

مقالات مرتبط جدید

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.