Penerapan Algoritma Label-Setting Untuk Menentukan Jalur Terpendek Dari Dua Node Pada Peta Kota Bandung

Persoalan pencarian rute terpendek di kota Bandung khususnya sangatbr /

diperlukan bagi wisatawan dalam dan luar kota Bandung sendiri. Mengingatbr /

banyaknya jalan yang dapat ditempuh membuat pengguna mencari jalur tercepatbr /

untuk sampai ke tujuannya.br /

Salah satu algoritma yang dapat digunakan untuk menyelesaikan masalahbr /

pencarian jalur terpendek ini adalah algoritma label-setting. Algoritma labelsettingbr /

melihat kemungkinan - kemungkinan yang ada dan menandai jalurbr /

terpendek ke node-n dengan mencari nilai minimum yang didapat untuk sampaibr /

ke node tersebut dan menandainya dengan menggunakan path tree.br /

Sebuah Path tree pada jalur terpendek, dalam teori graf adalah subgraf yangbr /

menghitung jarak antar node dari node asal ke node - node yang ada disekitarnyabr /

dan memilih nilai terkecil. Disebut tree karena jika menemukan dua buah jalurbr /

dengan jalur akhir yang sama (berputar), maka kita dapat menghapus jalur yangbr /

memiliki panjang jalur yang terbesar. Oleh karena itu path tree bersifat unik[6].br /

Beberapa pengujian telah dilakukan pada program algoritma label-settingbr /

dengan jumlah node sebanyak 59 node, 75 node dan 100 node. Selain itu jugabr /

mencoba ketiga jumlah node tersebut pada 2 buah PC yang memiliki spesifikasibr /

yang berbeda. Dari hasil pengujian dapat dilihat bahwa rata - rata waktu prosesbr /

algoritma label-setting untuk pencarian jalur terpendek adalah dibawah 1 detik.

Search for the shortest route problem in the city especially indispensablebr /

for travelers in and out of the city itself. Given the many roads that can be taken tobr /

make the user look for the fastest path to get to its destination.br /

One algorithm suitable to solve the problem of finding the shortest path isbr /

a label-setting algorithms. Label-setting algorithm see the possibilities -br /

possibilities that exist and mark the shortest path to node n by finding thebr /

minimum value obtained for up to the node and mark it by using the path tree.br /

A Path on the shortest path tree, in graph theory is the subgraph that calculates thebr /

distance between the node from the origin node to node - the node that is aroundbr /

and choose the smallest value. Called a tree because if it finds two paths to thebr /

same end of the line (rotating), then we can delete the path that has the largestbr /

path length. Therefore, the path tree is unique[6].br /

Several tests have been performed on the label-setting algorithm programbr /

by the number of nodes as many as 59 nodes, 75 nodes and 100 nodes. It alsobr /

tried a third the number of nodes on two PCs that have different specifications.br /

From the test results can be seen the performance of the label-setting algorithmsbr /

for shortest path problems.