Pembobotan ulang pada graf berbobot negatif untuk menerapkan algoritma dijkstra dalam menentukan lintasan terpendek

ABSTRAK:

Algoritma Dijkstra merupakan algoritma untuk mencari lintasan terpendek yang bekerja secara optimal pada graf berbobot non-negatif. Namun, dalam berbagai permasalahan nyata seperti sistem transportasi dan jaringan keuangan, sering ditemukan sisi dengan bobot negatif yang menyebabkan Algoritma Dijkstra tidak dapat diterapkan secara langsung. Penelitian ini bertujuan untuk mengatasi keterbatasan tersebut dengan menerapkan metode pembobotan ulang menggunakan Algoritma Johnson. Metode ini mengombinasikan Algoritma Bellman-Ford dan Dijkstra untuk mengubah bobot negatif menjadi non-negatif tanpa mengubah struktur solusi optimal. Data yang digunakan berupa dua graf acak berarah yang masing-masing terdiri dari 31 simpul, yang dibuat menggunakan algoritma Erdos-Renyi. Hasil penelitian menunjukkan bahwa pembobotan ulang berhasil membuat bobot graf menjadi non-negatif sehingga Algoritma Dijkstra dapat diterapkan, dan hasil lintasan terpendek yang diperoleh sama dengan hasil dari Algoritma Bellman-Ford. Dengan demikian, metode pembobotan ulang menggunakan Algoritma Johnson terbukti efektif dalam menangani bobot negatif dan tetap menjaga keakuratan hasil pencarian lintasan terpendek menggunakan Algoritma Dijkstra.

ABSTRACT:

Dijkstra's algorithm is an algorithm for finding the shortest path that works optimally on non-negative weighted graphs. However, in various real problems such as transportation systems and financial networks, edges with negative weights are often found which cause the Dijkstra Algorithm to be unable to be applied directly. This study aims to overcome these limitations by implementing a reweighting method using the Johnson Algorithm. This method combines the Bellman-Ford and Dijkstra Algorithms to change negative weights to non-negative without changing the structure of the optimal solution. The data used are two random directed graphs, each consisting of 31 nodes, which are created using the Erdos-Renyi algorithm. The results of the study show that reweighting successfully makes the graph weights non-negative so that the Dijkstra Algorithm can be applied, and the shortest path results obtained are the same as the results of the Bellman-Ford Algorithm. Thus, the reweighting method using the Johnson Algorithm is proven to be effective in handling negative weights and maintaining the accuracy of the shortest path search results using the Dijkstra Algorithm.

مستخلص البحث:

خوارزمية ديكسترا هي خوارزمية لإيجاد أقصر مسار تعمل على النحو الأمثل على الرسوم البيانية المرجحة غير السالبة. ومع ذلك، في مشاكل العالم الحقيقي مثل أنظمة النقل والشبكات المالية، غالبًا ما يتم العثور على حواف ذات أوزان سالبة مما يجعل خوارزمية ديجكسترا غير قابلة للتطبيق بشكل مباشر. هدف هذا البحث إلى التغلب على هذه القيود من خلال تطبيق طريقة إعادة الترجيح باستخدام خوارزمية جونسون. وتجمع هذه الطريقة بين خوارزمية بليمان فرودوخوارزمية ديجكسترا لتحويل الأوزان السالبة إلى غير سالبة دون تغيير بنية الحل الأمثل. البيانات المستخدمة هي عبارة عن رسمين بيانيين عشوائيين موجهين يتألف كل منهما من ٣١رأسًا، تم إنشاؤهما باستخدام خوارزمية إردوس-ريني. تُظهر النتائج أن إعادة الترجيح تنجح في جعل أوزان الرسم البياني غير سالبة بحيث يمكن تطبيق خوارزمية ديجكسترا، كما أن نتائج أقصر المسارات التي تم الحصول عليها هي نفسها نتائج خوارزمية بيلمان-فورد. وبالتالي، أثبتت طريقة إعادة الترجيح باستخدام خوارزمية جونسون فعاليتها في التعامل مع الأوزان السالبة مع الحفاظ على دقة نتائج إيجاد أقصر مسار باستخدام خوارزمية ديكسترا