Implementasi Aplikasi Pencarian Rute Berbasis Top-K Shortest Path Dengan Keragaman Untuk Perangkat Bergerak

Indraswara, Bramastya Dewa (2019) Implementasi Aplikasi Pencarian Rute Berbasis Top-K Shortest Path Dengan Keragaman Untuk Perangkat Bergerak. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.

[img]
Preview
Text
05111540000130-Undergraduate_Thesis.pdf

Download (1MB) | Preview

Abstract

Shortest path merupakan rute dengan jarak atau total bobot terkecil dari suatu vertex ke vertex lain pada suatu graf. Masalah shortest path sendiri merupakan masalah umum yang dapat ditemukan pada kehidupan sehari-hari. Baik dalam navigasi sampai kepada routing pada jaringan. Banyak sekali algoritma yang dapat digunakan untuk mencari shortest path pada sebuah graf. Setiap jenis graf memiliki algoritma yang optimal dalam menyelesaikan masalah ini. Tujuan dari pembuatan tugas akhir ini adalah untuk mendesain algoritma yang dapat mencari k shortest path yang cukup berbeda antara satu dengan lainnya berdasarkan preferensi pengguna. Selain itu, algoritma ini dapat memberikan shortest path yang memenuhi kebutuhan dan keinginan pengguna karena adanya tag-tag yang dapat dimasukkan pengguna dalam pencarian shortest path. Tag-tag tersebut digunakan sebagai salah satu patokan dalam mengurutkan tingkat kesesuaian rute. Jadi, rute dengan jarak yang kecil, jika pengguna lebih menginginkan tagnya terpenuhi, bisa saja berada pada urutan yang rendah jika rute tersebut tidak memenuhi tag yang diberikan pengguna. ================================================================================================ Shortest path is a path with the shortest distance or total weight between two vertices within a graph. Shortest path problem itself is a general problem that can be found in daily life problem, Be it for navigation to network routing. There are many algorithms that have been implemented to find the shortest path within a graph, Each type of graph has its own algorithm that can be used to solved this problem optimally. The goals of this research is to design algorithm that can find k shortest path which diverse from each other based on user preferences. In addition, this algorithm can provide a shortest path that meets the needs and desires of users because of the tags that users can enter in searching for the shortest path. These tags are used as one of the criterions in order to sort the level of suitability of the path. So, a path with a small distance, if the user wants more tags to be fulfilled, could be in a low order if the path does not meet the tag given by the user.

Item Type: Thesis (Undergraduate)
Additional Information: RSIf 006.76 Ind i-1 2019
Uncontrolled Keywords: Shortest Path, Path Finding, Road Network
Subjects: Q Science > QA Mathematics > QA166 Graph theory
Q Science > QA Mathematics > QA76.774.A53 Android
T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK5105.585 TCP/IP (Computer network protocol)
T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK5105.888 Web sites--Design. Web site development.
Divisions: Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User: Bramastya Dewa Indraswara
Date Deposited: 26 Apr 2022 03:53
Last Modified: 26 Apr 2022 03:55
URI: https://repository.its.ac.id/id/eprint/60794

Actions (login required)

View Item View Item