Dewi Wahyuningsih (2009) Penyelesaian masalah lintasan terpendek (shortest path) dengan menggunakan algoritma Johnson / Dewi Wahyuningsih. Diploma thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
Teori graph adalah salah satu cabang dari ilmu matematika yang sangat penting dan banyak sekali aplikasinya. Salah satunya adalah penyelesaian masalah lintasan terpendek. Ada beberapa metode yang sudah ada dan sering digunakan untuk menyelesaikan masalah lintasan terpendek misalnya Algoritma Dijkstra Algoritma Bellman Ford dan Algoritma Floyd-Warshall. Selain menggunakan metode-metode tersebut ada metode lain yang dapat digunakan untuk menyelesaikan masalah lintasan terpendek yaitu Algoritma Johnson. Dalam skripsi ini dibahas tentang penyelesaian masalah lintasan terpendek (shortest path) dengan menggunakan Algoritma Johnson. Langkah awal penyelesaian Algoritma Johnson adalah mengkonstruksi digraph baru dengan menambahkan titik baru pada digraph dan memberi bobot sisi yang keluar dari titik baru tersebut dengan 0. Langkah selanjutnya adalah mencari lintasan terpendek dari titik baru ke semua titik lain. Lintasan terpendek tersebut digunakan untuk mengubah bobot semua sisi pada digraph baru agar bobot semua sisi bernilai positif. Setelah itu mencari lintasan terpendek dari tiap titik ke semua titik lain dan mengubah hasilnya dengan menggunakan lintasan terpendek dari titik baru ke semua titik lain. Hasil dari perhitungan ini berupa matriks. Dari matriks ini dapat diketahui panjang lintasan terpendek dari tiap titik ke semua titik lain. Untuk menghitung lintasan terpendek dari titik baru ke semua titik lain yang berguna untuk mengubah semua bobot menjadi positif digunakan Algoritma Bellman-Ford. Untuk menghitung lintasan terpendek dari tiap titik ke semua titik lain yang semua bobot sisinya sudah bernilai positif digunakan Algoritma Dijkstra. Kelebihan Algoritma Johnson ini adalah dapat digunakan untuk digraph yang berbobot negatif dan untuk menyelesaikan masalah lintasan terpendek dari tiap titik ke semua titik lain.Untuk memeriksa kebenaran perhitungan dari Algoritma Johnson dapat digunakan Algoritma Floyd-Warshall. Dari proses perhitungan diperoleh hasil yang sama antara penyelesaian masalah lintasan terpendek dengan menggunakan Algoritma Johnson dan Algoritma Floyd-Warshall. Untuk memeriksa perhitungan secara manual dalam skripsi ini juga digunakan program bantu GIDEN.
| Item Type: | Thesis (Diploma) |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Fakultas Matematika dan IPA (FMIPA) > Departemen Matematika (MAT) > S1 Matematika |
| Depositing User: | library UM |
| Date Deposited: | 13 Jan 2009 04:29 |
| Last Modified: | 09 Sep 2009 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/16750 |
Actions (login required)
 |
View Item |