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

Jauhari, Mohammad Nafie, Nashichuddin, Ach. ORCID: https://orcid.org/0009-0006-8273-8878 and Salsabillah, Natasya Thalia (2025) Pembobotan ulang pada graf berbobot negatif untuk menerapkan algoritma dijkstra dalam menentukan lintasan terpendek. Jurnal Riset Mahasiswa Matematika, 5 (1). pp. 29-40. ISSN 2808-4926

Preview

Text 25945.pdf - Published Version Available under License Creative Commons Attribution Share Alike. Download (863kB) | Preview

Abstract

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.

Item Type:	Journal Article
Keywords:	Algoritma Dijkstra; Bobot Negatif; Pembobotan Ulang; Algoritma Johnson; Lintasan Terpendek.
Subjects:	01 MATHEMATICAL SCIENCES > 0101 Pure Mathematics > 010104 Combinatorics and Discrete Mathematics (excl. Physical Combinatorics)
Divisions:	Faculty of Mathematics and Sciences > Department of Mathematics
Depositing User:	Mohammad Nafie Jauhari
Date Deposited:	12 Dec 2025 08:22

Downloads

Origin of downloads

Actions (login required)

View Item