تصميم خوارزمية بزمن خطي لإيجاد المسار الاقصر في البيان

نقدم في هذا البحث خوارزمية فعالة لإيجاد المسار الأقصر في بيان متعدد المنابع, و ذلك باختيار المسار بين المنبع و المسافة التي تعطي طول المسار الأقل وصولا إلى المصب. تعتمد هذه الخوارزمية على مبدأ التكرار للوصول إلى الحل الأمثل لمسألة المسار الأقصر, حيث يتم تكرار خطوات الخوارزمية على جميع الأسهم في البيان. أثبتنا بأن زمن تنفيذ الخوارزمية المقترحة في هذا البحث هو زمن خطي قدره (O(n+L و هو يعتبر أفضل أزمنة الخوارزميات على الإطلاق.

In this paper, we introduce an Effective algorithm to find the shortest path in Multiple – Source Graph, by choosing the path between the source and the distance that gives at least the length of the path down to the sink. This algorithm is based on the principle of iteration to access the optimal solution of the shortest-path problem, Where the algorithm steps are repeated for all the darts in the Graph. We proved that the time of implementation of the proposed algorithm in this paper is linear time O(n+L) and This is considered the best times of the algorithms at all.