research centers


Search results: Found 1

Listing 1 - 1 of 1
Sort by

Article
DESIGN AND IMPLEMENTATION OF SHORTEST PATH ALGORITHM FOR NETWORK OF ROADS
تصميم وتنفيذ خوارزمية اقصر مسار لشبكة الطرق

Author: Nadia Moqbel Hassan
Journal: Journal of Engineering and Sustainable Development مجلة الهندسة والتنمية المستدامة ISSN: 25200917 Year: 2015 Volume: 19 Issue: 6 Pages: 77-88
Publisher: Al-Mustansyriah University الجامعة المستنصرية

Loading...
Loading...
Abstract

In this paper a new method programmed computerizing has been suggested which depends on converting the roads network to matrix and the representation of this matrix in adjacency matrix, that a number of rows is equal number of columns, where the degree of this matrix is equal for number of the edges plus one in (i) multiplied by number of the edges plus one in (j) of the roads network (graph). The elements of This matrix will be either (1) that means existing edge of orientation in one direction connecting between two nodes continuous connection, or (0) and that means there is no edge of oriented connecting between two nodes. And this converting has been implemented by using new algorithm characterized by finding the shortest path between two nodes in the roads network ,whatever its size, type and complication degree, in specific lengths, costs and terms and for more accuracy, to implement this algorithm, the matrix has been processed by three basic steps: The first step is to know and determine a number of the paths in the network and it is the first data which must be input to the computer in running the program. The second step is to specify the edges within installation, each path and its numbers. And the third step is to compare between the lengths of the calculated paths to find the shortest path. The results of this proposed algorithm have shown that it has very high efficiency to get very accurate results. The algorithm has been proven to reduce the size of the input data to the computer as well as to the time and effort to find the shortest path between two nodes in the designed network.

في هذا البحث تم اقتراح طريقة جديدة مبرمجة حاسوبيا تعتمد على تحويل شبكة الطرق ) Network roads ( إلى مصفوفة ثنائيةمربعة ) Matrix ( وتمثيل هذه المصفوفة بطريقة مصفوفة التجاور ) Adjacency Matrix (، أي إن عدد الصفوف مساوي لعدد ألأعمدة حيث إندرجة هذه المصفوفة ) Degree ( مساوي لعدد الحافات + 1 في ) i ( مضروبا في عدد الحافات + 1 في ) j ( في شبكة الطرق أي ) Graph .)وعناصر هذه المصفوفة تكون إما ) 1 ( وهذا يعني وجود حافة موجه باتجاه واحد تربط بين نقطتين ارتباط متواصل أو ) 0( وهذا يعني انه لا توجدحافة موجه تربط بين نقطتين. وقد تم تنفيذ هذا التحويل باستخدام خوارزمية جديدة والتي تتميز بإيجاد اقصر الطرق بين نقطتين في شبكةالطرق،مهما كان حجمها ونوعها ومهما كانت درجة تقعيدها بأطوال وكلف وفترة زمنية معينة. ولزيادة دقة تنفيذ هذه الخوارزمية تمت معالجةالمصفوفة بثلاث خطوات أساسيه الخطوة الأولى هي لمعرفة وتحديد عدد المسارات في الشبكة وهي أولى البيانات التي يجب إدخالها للحاسوبعند تشغيل البرنامج. والخطوة الثانية هي لتحديد الحافات الداخلة في تركيب كل مسار وعددها. والخطوة الثالثة للمقارنة بين أطوال المساراتالمحسوبة في هذه الخطوة لتحديد اقصر مسار. وقد أظهرت النتائج لهذه الخوارزمية المقترحة بأنها ذات كفاءة عالية جدا في الحصول علىالنتائج بدقة متناهية. وأثبتت الخوارزمية تقليل حجم البيانات المدخلة إلى الحاسوب بالإضافة إلى تقليل الوقت والجهد لإيجاد اقصر الطرق بيننقطتين في الشبكة المصممة.

Listing 1 - 1 of 1
Sort by
Narrow your search

Resource type

article (1)


Language

English (1)


Year
From To Submit

2015 (1)