Text

Algoritma Bellman-Ford-Dijkstra (BFD) Untuk Menentukan Lintasan Terpendek Pada Graf

---

ABSTRAK

Masalah lintasan terpendek adalah masalah yang berkaitan dengan penjumlahan bobot-bobot sisi pada graf. Pada tugas akhir ini dibahas suatu penyelesaian masalah lintasan terpendek pada graf yang memuat bobot sisi negatif, namun tidak memuat sikel dengan bobot sisi negatif. Metode yang digunakan yaitu metode Bellman-Ford-Dijkstra (BFD) dimana metode tersebut adalah gabungan antara metode Bellman-Ford dan metode Dijkstra. Penyelesaian metode tersebut menggunakan metode Dijkstra yang dimodifikasi pembaharuan nilai titik terpilih dengan metode Bellman-Ford, dimana metode ini memiliki penyelesaian algoritma yang lebih efisien karena membutuhkan jumlah operasi yang lebih sedikit daripada algoritma Bellman-Ford. Dari hasil penerapan metode BFD di Disparta Kabupaten Semarang diperoleh pohon lintasan terpendek yang menunjukkan hasil lintasan terpendek dari titik awal wisata ke semua titik wisata lain di graf Disparta.

Kata Kunci : Masalah Lintasan Terpendek, Jaringan Graf Berarah Asiklik, Bellman-Ford-Dijkstra
 
ABSTRACT

The shortest path problem is a problem related to the sum of edges weights in a graph. In this final project disscused on a graph containing a negative edges weights, but does not contain a cycle with a negative esges weughts. The method used is Bellman-Ford-Dijkstra (BFD) method where the method is a combination of Bellman-Ford method and Dijkstra method. The completion of the method uses the Dijkstra method which is modified by updating the selected vertex value with the Bellman-Ford method, where this method has more efficient algorithm completion because it requires fewer operations than the Bellman-Ford algorithm. From the results of the BFD method implementation in Semarang Regency Goverment Tourism office network, the graph has the shortest path tree which is the results of the shortest path from the starting point of travel to all other tourist points are obtained from the Semarang Regency Goverment Tourism.

Keywords : Shortest Path Problem, Direct Acyclic Graph Network, Bellman-Ford-Dijkstra

---

Ketersediaan

2200A19III

2200 A 19-ii

Perpustakaan FSM Undip (Referensi)

Tersedia

Informasi Detail

Judul Seri

MATEMATIKA

No. Panggil

2200 A 19-ii

Penerbit

: ., 2019

Deskripsi Fisik

-

Bahasa

Indonesia

ISBN/ISSN

-

Klasifikasi

530.12

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

-

Info Detail Spesifik

-

Pernyataan Tanggungjawab

Robby Rodhiyya

Versi lain/terkait

Lampiran Berkas

Komentar

---

Anda harus masuk sebelum memberikan komentar