Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn efficient algorithm for finding a shortest paths for all vertices in graph
خوارزمية فعالة لإيجاد المسارات الأقصر لجميع العقد في البيان
4155
1 128
0
(
0
)
Authors
محسن حسين( باحث )
Created by
zeina alrostum
Ask ChatGPT about the research
مسألة المسار الأقصر لجميع العقد في البيان هي , بلا شك , واحدة من أكثر المسائل الأساسية في خوارزميات نظرية البيان . نقدم في هذا البحث خوارزمية بسيطة و فعالة من أجل مسألة المسارات الأقصر في بيان موجه ( أو غير موجه ) . في هذه المسألة نقوم بإيجاد المسار الأقصر من عقدة منبع معطاة إلى جميع العقد الأخرى في هذا البيان و الذي يكون المسار الأقصر فيه هو المسار الذي يملك أقل كلفة ( أي مجموع أوزان الأضلاع ) . أثبتنا بأن تعقيد الخوارزمية المقترحة في هذا البحث يعتمد فقط على أضلاع البيان , و بينا بأن زمن تنفيذها هو زمن خطي قدره (O(m , و هذا يعتبر أفضل أزمنة الخوارزميات على الإطلاق . ثم أجرينا مقارنة بين تعقيد الخوارزمية المقترحة و تعقيد الخوارزمية المقترحة هو الأفضل .
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 this 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.
Artificial intelligence review:
Research summary
تتناول هذه الورقة البحثية مسألة إيجاد المسارات الأقصر لجميع العقد في بيان موجه أو غير موجه. يقدم الباحث د. محسن حسين خوارزمية جديدة وفعالة لهذه المسألة، حيث يتم إيجاد المسار الأقصر من عقدة منبع معينة إلى جميع العقد الأخرى في البيان. تعتمد الخوارزمية المقترحة على زمن خطي قدره O(m)، مما يجعلها من أفضل الخوارزميات من حيث زمن التنفيذ. تم إجراء مقارنة بين تعقيد الخوارزمية المقترحة وتعقيد الخوارزميات الشهيرة الأخرى، وتبين أن الخوارزمية المقترحة هي الأفضل. كما تم تقديم مثال توضيحي لعمل الخوارزمية وتحليل شامل لدرجة تعقيدها وزمن تنفيذها. الخوارزمية المقترحة تتميز بأنها بسيطة وسهلة التنفيذ ويمكن برمجتها حاسوبياً بسهولة، كما يمكن تطبيقها على بيانات كبيرة الحجم.
Critical review
دراسة نقدية: تعتبر هذه الورقة البحثية إضافة قيمة لمجال نظرية البيان وخوارزميات المسار الأقصر. ومع ذلك، هناك بعض النقاط التي يمكن تحسينها. أولاً، كان من الممكن تقديم المزيد من الأمثلة العملية لتوضيح كيفية تطبيق الخوارزمية على بيانات حقيقية. ثانياً، لم يتم التطرق بشكل كافٍ إلى كيفية تعامل الخوارزمية مع البيانات التي تحتوي على أوزان سالبة، وهو ما يمكن أن يكون تحدياً في بعض التطبيقات. أخيراً، كان من الممكن تقديم تحليل أكثر تفصيلاً لمقارنة الأداء بين الخوارزمية المقترحة والخوارزميات الأخرى في ظروف مختلفة.
Questions related to the research
-
ما هي المسألة الرئيسية التي تتناولها الورقة البحثية؟
المسألة الرئيسية هي إيجاد المسارات الأقصر لجميع العقد في بيان موجه أو غير موجه.
-
ما هو زمن تنفيذ الخوارزمية المقترحة؟
زمن تنفيذ الخوارزمية المقترحة هو زمن خطي قدره O(m).
-
ما هي الميزة الرئيسية للخوارزمية المقترحة مقارنة بالخوارزميات الأخرى؟
الميزة الرئيسية هي أن زمن تنفيذها خطي، مما يجعلها من أفضل الخوارزميات من حيث زمن التنفيذ.
-
هل يمكن تطبيق الخوارزمية على بيانات كبيرة الحجم؟
نعم، يمكن تطبيق الخوارزمية على بيانات كبيرة الحجم لأن زمن تنفيذها لا يعتمد على عدد العقد في البيان.
References used
Allulli. L, Lichodzijewski .P and Zeh. N, "A Faster Cache- Oblivious Shortest-Path Algorithm for Undirected Graphs with Bounded Edge Lengths", www.web.cs.dal.ca
BASWANA. S AND KAVITHA. T, "FASTER ALGORITHMS FOR ALL-PAIRS APPROXIMATE SHORTEST PATHS IN UNDIRECTED GRAPHs", Jornal of ACM,52(1), pp 1- 24. 2005. www.cse.iitk.ac.in
Bernstein. A, "Near Linear Time (1 + ϵ)-Approximation for Restricted Shortest Paths in Undirected Graphs", siam, 2011
Brandes. U, "A Faster Algorithm for Betweenness Centrality", Journal of Mathematical Sociology 25(2):163-177, (2001)
rate research
Read More
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.
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.
There has been a clear and rapid development in signal processing systems,
this development comes as a result of the availability of modern techniques
in electronic systems and also as a result of achieving mathematical
algorithms which were effec
tive and perfect for signal processing.
One of the most important application in signal processing is the digital
image processing techniques. Sampling process is regarded as one of the
basic and important operations in signal processing, from which we obtain
samples that can represent the original image in perfect way.
We present in this essay an affective algorithm which helps to arrange onedimensional
samples from two- dimensional samples image. This enables to
obtain a series of samples which has an ability of representing images with
concern of their general structure. Also the neighborhood correlation of
image points is respected, in addition to carrying out the subsequent
treatments with less mathematical cost.
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.
As it’s known, The Graph k-Colorability Problem (GCP) is a wellknown
NP-Hard Problem. This problem consists in finding the k
minimum number of colors to paint the vertices of a graph in such a way
that any two adjoined vertices, which are connecte
d by an edge, have
always different colors. In another words how can we color the edges of a
graph in such a way that any two edges joined by a vertex have always
different colors? In this paper we introduce a new effective algorithm for
coloring the edges of the graph. Our proposed algorithm enables us to
achieve a Continuously Edge Coloring (CEC) for a set of known graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
