Article Per Year (5 Year)
p-Index From 2021 - 2026
0.23
P-Index
This Author published in this journals
All Journal Jurnal Riset Mahasiswa Matematika
Salsabillah, Natasya Thalia
Unknown Affiliation
Mathematics

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
Pembobotan Ulang pada Graf Berbobot Negatif untuk Menerapkan Algoritma Dijkstra dalam Menentukan Lintasan Terpendek Salsabillah, Natasya Thalia; Jauhari, Mohammad Nafie; Nashichuddin, Achmad
Jurnal Riset Mahasiswa Matematika Vol 5, No 1 (2025): Jurnal Riset Mahasiswa Matematika
Publisher : Mathematics Department, Maulana Malik Ibrahim State Islamic University of Malang

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.18860/jrmm.v5i1.34383

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.
Co-Authors Ach. Nashichuddin Mohammad Nafie Jauhari