Skripsi

Penyelesaian masalah lintasan terpendek (shortest path) dengan menggunakan algoritma Johnson / Dewi Wahyuningsih

Abstrak
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.

Informasi Detail

DDC

Rs 511.8 DEW p

Prodi

Skripsi (Sarjana)--Universitas Negeri Malang. Program Studi Matematika, 2007.

Deskripsi Fisik

ix, 114 hlm : il. ; 29 cm

Bahasa

Indonesia

No Reg

01039/KI/07

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang, 2007

Subjek

1. ALGORITMA JOHNSON - APLIKASI
2. LINTASAN TERPENDEK

Pembimbing

1. SAPTI WAHYUNINGSIH ; 2. DARMAWAN SATYANANDA

Lampiran Berkas