Praadha, Muhammad Pandu (2020) Desain dan Analisis Algoritma untuk Mendapatkan Aliran Maksimal pada Graf Tidak Berarah dan Berbobot dalam Penyelesaian Permasalahan SPOJ ADAHOSE - Ada and Hose. Other thesis, InstitutTeknologi Sepuluh Nopember.
Preview |
Text
05111540000128-Undergraduate_Thesis.pdf Download (2MB) | Preview |
Preview |
Text
05111540000128-Approval.pdf Download (444kB) | Preview |
Abstract
Permasalahan dalam buku Tugas Akhir ini diambil dari dunia nyata namun sudah disederhanakan ke dalam bentuk soal yang terdapat pada situs Sphere Online Jugde “ADAHOSE – Ada and Hose”.Dalam permasalahan ini, diketahui bahwa Ada, seorang petani, memiliki sebuah ladang dengan selang yang mengelilingi tiap 1×1 bidang ladang.Terdapat pula sebuah sumur dan alat penyiram di atas dan di bawah ladang masing-masing.Selain itu selang yang sangat besar mengarah dari sumur ke atas ladang dan dari bawah ladang ke alat penyiram.Ada ingin menghitung total aliran-per-waktu yang mengalir dari sumur ke alat penyiram.
Tugas Akhir ini akan diimplementasikan dengan metode pencarian jalan terpendek pada sebuah graf tidak berarah dan berbobot. Penulis memilih algoritma Dijkstra dengan pertimbangan, algoritma Dijkstra merupakan metode pencarian jalan terpendek yang cepat dan menghasilkan solusi yang benar.
Dalam buku ini akan dibahas implementasi algoritma Dijkstra untuk mencari aliran maksimal dari sumur ke alat penyiram tersebut dengan menggunakan bahasa pemrograman C++. Dari serangkaian percobaan yang telah dilakukan, didapatkan kesimpulan bahwa algoritma yang dirancang adalah sesuai dengan permasalahan ini dan algoritma tersebut dipengaruhi secara kuadrat oleh ukuran ladang.
| Item Type: | Thesis (Other) |
|---|---|
| Uncontrolled Keywords: | maximum flow, undirected graph, weighted graph, aliran maksimal, graf tak berarah, graf berbobot. |
| Subjects: | Q Science > QA Mathematics > QA9.58 Algorithms |
| Divisions: | Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering |
| Depositing User: | Muhammad Pandu Praadha |
| Date Deposited: | 18 Sep 2020 08:59 |
| Last Modified: | 23 Jun 2023 13:26 |
| URI: | http://repository.its.ac.id/id/eprint/81985 |
Actions (login required)
 |
View Item |