<![CDATA[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.]]>
Copyrights © 2025
