Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDesign a linear time Algorithm for Finding A shortest path in Graph
تصميم خوارزمية بزمن خطي لإيجاد المسار الاقصر في البيان
2715
4 233
0
(
0
)
Authors
ناصر أبو صالح( باحث )
Created by
Shamra Editor
Ask ChatGPT about the research
نقدم في هذا البحث خوارزمية فعالة لإيجاد المسار الأقصر في بيان متعدد المنابع, و ذلك باختيار المسار بين المنبع و المسافة التي تعطي طول المسار الأقل وصولا إلى المصب. تعتمد هذه الخوارزمية على مبدأ التكرار للوصول إلى الحل الأمثل لمسألة المسار الأقصر, حيث يتم تكرار خطوات الخوارزمية على جميع الأسهم في البيان. أثبتنا بأن زمن تنفيذ الخوارزمية المقترحة في هذا البحث هو زمن خطي قدره (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.
Artificial intelligence review:
Research summary
يقدم هذا البحث خوارزمية فعالة لإيجاد المسار الأقصر في بيان متعدد المنابع، وذلك من خلال اختيار المسار بين المنبع والمسافة التي تعطي طول المسار الأقل وصولاً إلى المصب. تعتمد الخوارزمية على مبدأ التكرار للوصول إلى الحل الأمثل لمسألة المسار الأقصر، حيث يتم تكرار خطوات الخوارزمية على جميع الأسهم في البيان. أثبتت الدراسة أن زمن تنفيذ الخوارزمية هو زمن خطي قدره O(n + L)، مما يجعلها من أفضل الخوارزميات المتاحة. تتضمن الخوارزمية خطوتين أساسيتين: استبدال السهم بالسهم المعاكس له، وزيادة طول السهم المعاكس تدريجياً حتى يصل إلى طوله الأصلي. يتم تكرار هذه الخطوات على جميع الأسهم في البيان. تتميز الخوارزمية بسهولة التنفيذ وقلة عدد الخطوات اللازمة، مما يجعلها مناسبة للتطبيق في شبكات الأعمال المختلفة.
Critical review
دراسة نقدية: على الرغم من أن الخوارزمية المقترحة تقدم حلاً فعالاً لمسألة المسار الأقصر بزمن خطي، إلا أن هناك بعض النقاط التي يمكن تحسينها. أولاً، لم يتم التطرق بشكل كافٍ إلى كيفية التعامل مع البيانات الكبيرة والمعقدة التي قد تحتوي على عدد كبير من العقد والأقواس. ثانياً، لم يتم تقديم تحليل شامل لكيفية تأثير التغيرات في الأوزان على أداء الخوارزمية. ثالثاً، يمكن تحسين الخوارزمية لتكون أكثر تكيفاً مع الشبكات الديناميكية التي تتغير فيها الأوزان بشكل مستمر. وأخيراً، يمكن تقديم المزيد من الأمثلة العملية والتطبيقات الواقعية لتوضيح فعالية الخوارزمية بشكل أفضل.
Questions related to the research
-
ما هي الخطوتين الأساسيتين في الخوارزمية المقترحة؟
الخطوتين الأساسيتين هما استبدال السهم بالسهم المعاكس له، وزيادة طول السهم المعاكس تدريجياً حتى يصل إلى طوله الأصلي.
-
ما هو زمن تنفيذ الخوارزمية المقترحة؟
زمن تنفيذ الخوارزمية المقترحة هو زمن خطي قدره O(n + L).
-
ما هي التطبيقات العملية لمسألة المسار الأقصر؟
تملك مسألة المسار الأقصر تطبيقات عملية متعددة مثل شبكات النقل، شبكات الطرق، السكك الحديدية، شبكات التدفق (كهرباء، ماء، نفط، معلومات)، وشبكات الاتصالات.
-
ما هي ميزات الخوارزمية المقترحة؟
من أهم ميزات الخوارزمية المقترحة هي بساطة التنفيذ، الزمن الخطي للتنفيذ، قلة عدد الخطوات اللازمة، وصلاحيتها لجميع أنواع الشبكات مهما كان حجمها.
References used
A. Kolokolova " Bellman-Ford algorithm" Applied Algorithms February 14, 2012
Chandy. K. M and Misra. J " Distributed Computation on Graphs: Shortest Path Algorithms" Communications of the ACM , Volume 25, Number I 1, November 1982
(Dijkstra. . W, "A note on two problems in connexion with graphs", Numer Math 1, 269–271. (1959
rate research
Read More
The all-nodes shortest paths problem is undoubtedly one of
the most basic problems in algorithmic graph theory. In this paper,
we introduce simple and efficient algorithm for all nodes shortest
paths problem for directed (undirected) graphs. In th
is problem, we
find the shortest path from a given source node to all other nodes in
the graph, in which the shortest path is a path with minimum cost,
i.e., sum of the edge weights.
We proved that the complexity of the proposed algorithm in
this paper depends only on the edges graph, and we show that the
time of implementation of this algorithm is linear time O(m) and
This is considered the best times of the algorithms at all. And
a Comparison between complexity of proposed algorithm and the
famous shortest path algorithms have been made, and the obtained
results have shown that the complexity of the proposed algorithm
is best.
The shortest path problem can be categorized in to two
different problems; single source shortest path problem (SSSP) and
all pair shortest algorithm (APSP). In this paper, analysis and
comparison between complexity of the famous shortest path
al
gorithms have been made, and the obtained results have shown
that researchers have got remarkable success in designing better
algorithms in the terms of time complexity to solve shortest path
algorithms.
This paper illustrates a design of linear array antenna equal space and non uniform
excitation using Dolph – Chebyshev method , We will discuss the designing procedure
for antenna array having odd or even number of elements at two different values
of the
major to minor sidelobe level and at various between spaces , we will calculate the
excitation coefficients and plot the radiation pattern for each case in addition to calculate
both of the half power beam width angel and directivity. Finally : two curves will be
plotted : first of them for beam broadening factor as a function of the major to minor
sidelobe ratio ,the other one for directivity as a function of the array length.
We define a linear pregroup parser, by applying some key modifications to the minimal parser defined in (Preller, 2007). These include handling words as separate blocks, and thus respecting their syntactic role in the sentence. We prove correctness o
f our algorithm with respect to parsing sentences in a subclass of pregroup grammars. The algorithm was specifically designed for a seamless implementation in Python. This facilitates its integration within the DisCopy module for QNLP and vastly increases the applicability of pregroup grammars to parsing real-world text data.
The graph-theoretical thickness (shortly thickness)of graph G,
denoted by Φ(G), is the minimum number of planar subgraphs into
which the graph can be decomposed, and a graph that can be
drawn in the plane without any of its edges intersecting is c
alled a
planar graph. determining the thickness of a given graph is known
to be an NP-complete problem.
In this paper we introduce an application heuristic algorithm for
determining the thickness. Our algorithm is based on simulated
annealing optimization scheme which provide the results of the
New-thick (1). We show that the simulated annealing is a efficient
method to obtain good approximation for the thickness when the
number vertices are at most 30 otherwise it is slower.
Finally, we apply this algorithm on the heuristic algorithm Newthick
and we show that the algorithm produces a good
approximation and optimization solution for the thickness, and we
program this algorithm with C++, and running it by laptop has
RAM 2GB and CPU 2.27GHZ.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
