Depth First Search Algorithm In Solving the Shortest Route Using the Concept of Generate and Test

Alvendo Wahyu Aranski(1*),

(1) Institut Teknologi Batam
(*) Corresponding Author


Depth First Search Algorithm is a search process to find the right solution that requires short memory and time in finding the Goal. The problem in this research is the difficulty of salesmen to find alternative short routes to arrive at the final node as consideration for finding solutions. The purpose of this study is to find the shortest path so that salesmen can easily and quickly get to the final solution by saving time and mileage. The Generate And Test concept consists of combining the Depth first search algorithm with the backward tracking process. All processes must be completed before the testing process is carried out. If the General And Test process is carried out sequentially or systematically, it will get the best value in finding a solution, the weakness if the search process is large or extensive then the search process takes a very long time. How it works Generatr and test, namely 1. Generate possible solutions in the form of state states with the concept of a one-position path to the destination path. 2. Test, select whether the solution can be accepted according to the existing criteria 3. If the solution has got the Goal then the search is stopped, if not then the process is continued until finding a solution. The final result of testing the shortest route is A-B-E-J-P-S-U = 25+21+24+24+17+18=129

Full Text:



R. R. Pratama et al., “Penyelesaian Travelling Salesman Problem,” vol. 2, no. 1, 2020.

D. F. Sulistiyani et al., “Implementasi Algoritma Generate And Test Untuk Optimalisasi,” vol. 4, no. 2, pp. 106–114, 2021.

H. Maros and S. Juniar, “済無No Title No Title No Title,” pp. 1–23, 2016.

B. Prasetiyo and M. R. Hidayah, “Ipi355205,” vol. 1, no. 2, pp. 161–167, 2014.

M. Rahmasuci, H. Hotimatus, M. Azizah, P. Wulandari, D. Adistia, and S. Bukhori, “Strategi Menemukan Jalan Keluar Labirin dengan Waktu Tercepat Menggunakan Metode DFS,” Informatics Journal, vol. 2, no. 3, pp. 154–159, 2017.

S. Lailiyah, A. Yusnita, and T. A. Panotogomo, “Penerapan Algoritma Depth First Search Pada Sistem Pencarian Dokumen,” Snitt, pp. 174–179, 2017.

P. Mike, “Search Optimization of The Shortest Route Using the Generate And Test Algorithm,” vol. 6, no. 158, pp. 25–32, 2022.

R. Rahmadi, “Implementasi Metode Generate and Test Dalam Menyelesaikan Travelling Salesman Problem Menggunakan Robot Bersensor,” Seminar Nasional (SNATI), vol. 2010, no. Snati, pp. 29–34, 2010.

S. Welianto, R. G. Santosa, and A. R. Chrismanto, “Implementasi Algoritma Generate and Test Pada Pencarian Rute Terpendek,” Jurnal Informatika, vol. 7, no. 2, 2012, doi: 10.21460/inf.2011.72.103.



  • There are currently no refbacks.

Jumlah Kunjungan:

View My Stats

Published Papers Indexed/Abstracted By: